253. 会议室 II（会员题目）

题目

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

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

比如给你输入 meetings = [[0,30],[5,10],[15,20]]，算法应该返回 2，因为后两个会议和第一个会议时间是冲突的，至少申请两个会议室才能让所有会议顺利进行。
如果会议之间的时间有重叠，那就得额外申请会议室来开会，想求至少需要多少间会议室，就是让你计算同一时刻最多有多少会议在同时进行。
换句话说，如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间，仅此而已。
对于这种时间安排的问题，本质上讲就是区间调度问题，十有八九得排序，然后找规律来解决。
​​​关于差分数组内容​​ 差分模板类，直接调用即可

public class difference {
    private int[] diff;
    public  difference(int[] nums){
        diff = new int[nums.length];
        diff[0] = nums[0];
        for(int i = 1;i < diff.length;i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }
    public  void increment(int i,int j,int val){
        diff[i] += val;
        if(j + 1 < diff.length){
            diff[j+1] -= val;
        }
    }
    public int[] result(){
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

举例来说，如果输入 meetings = [[0,30],[5,10],[15,20]]，那么我们就给数组中 [0,30],[5,10],[15,20] 这几个索引区间分别加一，最后遍历数组，求个最大值就行了。差分数组技巧可以在 O(1) 时间对整个区间的元素进行加减，所以可以拿来解决这道题。

class solution{
 int[] diff;

public int minMeetingRooms(int[][] intervals) {

    int max = Integer.MIN_VALUE;

    for (int i = 0; i < intervals.length; i++) {
        max = Math.max(max, intervals[i][1]);
    }

    diff = new int[max];

    for (int i = 0; i < intervals.length; i++) {
        int k = intervals[i][0];
        int j = intervals[i][1] - 1;
        // int val = 1;
        increment(k, j, 1);
    }

    int[] res = result(diff);

    int result = 0;

    for (int i = 0; i < res.length; i++) {
        result = Math.max(result, res[i]);
    }
    return result
}
public void increment(int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < diff.length) {
        diff[j + 1] -= val;
    }
}

public int[] result(int[] df) {
    int[] res = new int[df.length];
    // 根据差分数组构造结果数组
    res[0] = df[0];
    for (int i = 1; i < df.length; i++) {
        res[i] = res[i - 1] + df[i];
    }
    return res;
}
}

优雅的方法：

把这些会议的时间区间进行投影，红色的点代表每个会议的开始时间点，绿色的点代表每个会议的结束时间点。

现在假想有一条带着计数器的线，在时间线上从左至右进行扫描，每遇到红色的点，计数器 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);

    // 扫描过程中的计数器
    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;
}