时间调度问题

给你输入若干形如[begin, end]的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。

// 返回需要申请的会议室数量
int minMeetingRooms(int[][] meetings);

比如给你输入meetings = [[0,30],[5,10],[15,20]]，算法应该返回 2，因为后两个会议和第一个会议时间是冲突的，至少申请两个会议室才能让所有会议顺利进行。
如果会议之间的时间有重叠，那就得额外申请会议室来开会，想求至少需要多少间会议室，就是让你计算同一时刻最多有多少会议在同时进行。
换句话说，如果把每个会议的起止时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间，也就是给你输入若干时间区间，让你计算同一时刻「最多」有几个区间重叠。
对于这种时间安排的问题，本质上讲就是区间调度问题，十有八九得排序，然后找规律来解决。
我们首先把这些会议的时间区间进行投影：

红色的点代表每个会议的开始时间点，绿色的点代表每个会议的结束时间点。
现在假想有一条带着计数器的线，在时间线上从左至右进行扫描，每遇到红色的点，计数器count加一，每遇到绿色的点，计数器count减一：

这样一来，每个时刻有多少个会议在同时进行，就是计数器count的值，count的最大值，就是需要申请的会议室数量。
如何实现
首先，对区间进行投影，就相当于对每个区间的起点和终点分别进行排序：

int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] begin = new int[n];
    int[] end = new int[n];
    // 把左端点和右端点单独拿出来
    for(int i = 0; i < n; i++) {
        begin[i] = meetings[i][0];
        end[i] = meetings[i][1];
    }
    // 排序后就是图中的红点
    Arrays.sort(begin);
    // 排序后就是图中的绿点
    Arrays.sort(end);
    // ...
}

然后就简单了，扫描线从左向右前进，遇到红点就对计数器加一，遇到绿点就对计数器减一，计数器count的最大值就是答案：

int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] begin = new int[n];
    int[] end = new int[n];
    for(int i = 0; i < n; i++) {
        begin[i] = meetings[i][0];
        end[i] = meetings[i][1];
    }
    Arrays.sort(begin);
    Arrays.sort(end);
    // 扫描过程中的计数器
    int count = 0;
    // 双指针技巧
    int res = 0, i = 0, j = 0;
    while (i < n && j < n) {
        if (begin[i] < end[j]) {
            // 扫描到一个红点
            count++;
            i++;
        } else {
            // 扫描到一个绿点
            count--;
            j++;
        }
        // 记录扫描过程中的最大值
        res = Math.max(res, count);
    }
    return res;
}

这里使用的是 双指针技巧，你可以认为指针 i 就是那根扫描线，根据i, j的相对位置就可以模拟扫描线前进的过程。