数组：区间问题

0056. 合并区间 (opens new window)

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

解析

扫描线算法，见 算法模板：区间合并。

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        
        sort(intervals.begin(), intervals.end());

        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > end) {
                ans.push_back({start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            } else {
                end = max(end, intervals[i][1]);
            }
        }
        ans.push_back({start, end});
        return ans;
    }
};

0057. 插入区间 (opens new window)

题目

给你一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

解析

由于原区间列表是无重叠的，因此只要找到与插入区间重叠的区间进行合并即可。

代码

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {
        vector<vector<int>> ans;
        int n = a.size(), i = 0;

        // 添加左侧不重叠区间
        while (i < n && a[i][1] < b[0]) {
            ans.push_back(a[i++]);
        }

        // 合并中间重叠区间
        if (i < n) {
            b[0] = min(a[i][0], b[0]);
            while (i < n && a[i][0] <= b[1]) {
                b[1] = max(a[i++][1], b[1]);
            }
        }
        ans.push_back(b);

        // 添加右侧不重叠区间
        while (i < n) {
            ans.push_back(a[i++]);
        }
        return ans;
    }
};

0252. 会议室 (opens new window)

题目

给定一个会议时间安排的数组 intervals，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi]，请你判断一个人是否能够参加这里面的全部会议。

解析

先按区间起始值排序，遍历区间，判断区间是否有交集即可。

代码

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        if (intervals.size() < 2) return true;

        sort(intervals.begin(), intervals.end(), cmp);

        for (int i = 1; i < intervals.size(); i ++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }

    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }
};

0253. 会议室 II (opens new window)

题目

给你一个会议时间安排的数组 intervals，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi]，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

解析

将开始时间和结束时间分别排序存入数组，之后遍历：

• 开始时间在结束时间之前：需要一个新的会议室；
• 开始时间在结束时间之后：释放一个会议室，判断下一个结束时间。

代码

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<int> starts, ends;
        for (int i = 0; i < intervals.size(); i ++) {
            starts.push_back(intervals[i][0]);
            ends.push_back(intervals[i][1]);
        }

        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());

        int ans = 0, end = 0;
        for (int i = 0; i < intervals.size(); i ++) {
            if (starts[i] < ends[end]) ans ++;
            else end ++;
        }
        return ans;
    }
};

0435. 无重叠区间 (opens new window)

题目

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

• 可以认为区间的终点总是大于它的起点。
• 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

解析

按照区间的右边界排序，由于右边界越小，留给之后可选择的范围越大，所以要优先选择右边界小的区间。

因此只需要从左向右记录非交叉区间的个数，最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() < 2) return 0;

        sort(intervals.begin(), intervals.end(), cmp);

        int count = 1, end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i ++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                count ++;
            }
        }
        return intervals.size() - count;
    }

    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[1] < b[1];
    }
};