区间问题

区间合并

56. 合并区间

Difficulty: 中等

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start<sub style="display: inline;">i</sub>, end<sub style="display: inline;">i</sub>] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10<sup>4</sup>
• intervals[i].length == 2
• 0 <= start<sub style="display: inline;">i</sub> <= end<sub style="display: inline;">i</sub> <= 10<sup>4</sup>

Solution

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());//排序
        int st = -1, ed = -1;//在所有区间范围左边
        vector<vector<int>> ans;
        for (auto seg : intervals) {
            if (ed < seg[0]) {//区间不相交
                if (st != -1) ans.push_back({st, ed});//跳过哨兵区间
                st = seg[0];//更新左端点
            } 
            ed = max(seg[1], ed); //更新右端点
        }
        if(st != -1) ans.push_back({st, ed});//加入最后维护的区间，特判输入不为空
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        vector<vector<int>> res;
        sort(a.begin(), a.end());
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < a.size(); i ++ ) {
            if (r < a[i][0]) {
                res.push_back({l, r});
                l = a[i][0], r = a[i][1];
            } else r = max(r, a[i][1]);
        }
        res.push_back({l, r});
        return res;
    }
};

57. 插入区间

Difficulty: 中等

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

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

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

• 0 <= intervals.length <= 10<sup>4</sup>
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10<sup>5</sup>
• intervals 根据 intervals[i][0] 按 升序 排列
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 10<sup>5</sup>

Solution

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(b[1], a[i++][1]);//若重叠则更新右端点
        }
        ans.push_back(b);
        while (i < n) ans.push_back(a[i++]);
        return ans;
    }
};

区间贪心

905. 区间选点

问题描述

给定 $N$ 个闭区间 $[a_i,b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 $N$，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

$1 \le N \le 10^5$,
$-10^9 \le a_i \le b_i \le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

算法分析

1. 将每个区间按照右端点从小到大进行排序

2. 从前往后枚举区间，ed值初始化为无穷小

   • 如果当前区间已经包含点，即包含掉上次区间的右端点，则pass直接进行下一轮循环
   • 否则，说明需要选择一个新的点，选择当前区间的右端点。 res ++ ; ed = range[i].r;

贪心证明

设 ans 为最优解， cnt为某一个答案。
欲证：ans = cnt

① ans <= cnt， 显然；
② ans >= cnt， 这里应该是容易产生困惑的地方。

首先要清楚一点，ans是一个定值、常数，表示最优解的值； 而cnt它是一个变量，代表某一种方案的值。

要证: ans >= cnt， 只需要证：ans >= max(cnt)即可，因为如果连最大的cnt都不超过ans，那么所有的cnt都小于等于ans。

何时取到 max？当全部区间两两不相交时，cnt必然取到最大值。（但是，有部分区间相交时，也可以取到最大值，设想一下只有 2 个区间，中间相交了一小部分，我们可以分别取第一个区间的最左，和第二个区间的最右。但这并不重要，只要我们能证明，在其中一种取到最大值的方案中，ans >= cnt，那么剩下的全部方案的cnt必然小于等于ans。）

显然，当全部区间两两不相交时，ans = cnt。

因此由ans >= max(cnt) >= cnt， 可证②也是成立的。

综上所述，由①②可知，ans = cnt。

Solution

右端点排序，正序遍历

#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int,int>;
const int N = 1e5 + 10;
PII range[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    } 
    sort(range, range + n,[&](const PII& a, const PII& b) {return a.second < b.second;});
    int ans = 0;
    for (int i = 0, ed = -2e9; i < n; ++i) {
        if (ed < range[i].first) {
            ++ans;
            ed = range[i].second;
        }
    }
    cout << ans;
    return 0;
}

左端点排序，正序遍历（逆序遍历则和上面右端点排序思路一样，对称即可）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Range{
    int l, r;
    bool operator< (const Range& R) {
        return l < R.l;
    }
}range[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    } 
    sort(range, range + n);
    int ans = 0;
    for (int i = 0, ed = -2e9; i < n; ++i) {
        if (ed < range[i].l) {//不相交
            ++ans;
            ed = range[i].r;
        } else {
            ed = min(ed, range[i].r);//因为是按左端点排序的，当前区间右端点不一定在上一区间右端点后面，可能不包含选择点（即上一区间右端点），需要回退
        }
    }
    cout << ans;
    return 0;
}

908. 最大不相交区间数量

问题描述

给定 $N$ 个闭区间 $[a_i,b_i]$，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

输入格式

第一行包含整数 $N$，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示可选取区间的最大数量。

数据范围

$1 \le N \le 10^5$,
$-10^9 \le a_i \le b_i \le 10^9$

输入样例：

-1 1
2 4
3 5

输出样例：

2

算法分析

最大不相交区间数==最少覆盖区间点数

因为如果几个区间能被同一个点覆盖，说明他们相交了，所以有几个点就是有几个不相交区间

Solution

#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int,int>;
const int N = 1e5 + 10;
PII range[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    }
    sort(range, range + n, [](const PII &a, const PII &b) {return a.second < b.second;});
    int ans = 0;
    for (int i = 0, ed = -2e9; i < n; ++i) {
        if (ed < range[i].first) {
            ans++;
            ed = range[i].second;
        }
    }
    cout << ans;
    return 0;
}

906. 区间分组

问题描述

给定 $N$ 个闭区间 $[a_i,b_i]$，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输出最小组数。

输入格式

第一行包含整数 $N$，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示最小组数。

数据范围

$1 \le N \le 10^5$,
$-10^9 \le a_i \le b_i \le 10^9$

输入样例：

-1 1
2 4
3 5

输出样例：

2

贪心决策

从前往后枚举每个区间，判断此区间能否将其放到现有的组中

1. 如果当前区间的左端点比最小组的最右端点要小，ranges[i].l<=heap.top() ， 就开一个新组 heap.push(range[i].r);

2. 如果当前区间的左端点比最小组的最右端点要大，则放在该组， heap.pop(), heap.push(range[i].r); 然后用右端点更大的当前区间右端点代表该组，即更新最小组的最右端点，这样heap有多少区间，就有多少组。

算法流程

区间分组，在组内区间不相交的前提下，分成尽可能少的组。
而不是尽可能多的组，因为一个区间一组，就是尽可能多组的答案。
等效于把尽可能多的区间塞进同一组，要满足range[i].l > heap.top。
heap 存储的是每个组的最右的端点，由于是小根堆heap.top()是对应的最小的最右点。

那如果遇到，塞不进去的情况呢？
就是heap.top >= range[i].l, 当前区间的左端点比最小的右端点还要小，放到任何一组都会有相交部分。
那就需要新开一组，heap.push(range[i].r)

1. 把所有区间按照左端点从小到大排序
2. 从前往后枚举每个区间，判断此区间能否将其放到现有的组中
3. heap有多少区间，就有多少组

Solution

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
struct Range{
    int l, r;
    bool operator< (const Range & R) const {
        return l < R.l;
    }
}range[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    }
    sort(range, range + n);
    priority_queue<int, vector<int>, greater<int>> heap;
    heap.push(range[0].r);
    for (int i = 1; i < n; ++i) {
        if (range[i].l <= heap.top()) heap.push(range[i].r);
        else {
            heap.pop();
            heap.push(range[i].r);
        }
    }
    cout << heap.size();
    return 0;
}

一次遍历，看成活动安排问题

有若干个活动，第 $i$ 个活动开始时间和结束时间是 [$S_i$,$f_i$]，同一个教室安排的活动之间不能交叠，求要安排所有活动，至少需要几个教室？

• 有时间冲突的活动不能安排在同一间教室，与该问题的限制条件相同，即最小需要的教室个数即为该题答案。

1. 把所有开始时间和结束时间排序
2. 遇到开始时间就把需要的教室加 1
3. 遇到结束时间就把需要的教室减 1
4. 在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数

• 还可以求出最多同时进行的活动数量的时间点
• 

Solution

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int t[2 * N], idx = 0;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        t[idx++] = 2 * a;
        t[idx++] = 2 * b + 1;
    }
    sort(t, t + idx);
    int ans = 0;
    for (int i = 0, cnt = 0; i < idx; ++i) {
        if (t[i] % 2 == 0) ++cnt, ans = max(ans, cnt);
        else --cnt;
    }
    cout << ans;
    return 0;
}

907. 区间覆盖

问题描述

给定 $N$ 个闭区间 $[a_i,b_i]$ 以及一个线段区间 $[s,t]$，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 $-1$。

输入格式

第一行包含两个整数 $s$ 和 $t$，表示给定线段区间的两个端点。

第二行包含整数 $N$，表示给定区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需最少区间数。

如果无解，则输出 $-1$。

数据范围

$1 \le N \le 10^5$,
$-10^9 \le a_i \le b_i \le 10^9$,
$-10^9 \le s \le t \le 10^9$

输入样例：

1 5
-1 3
2 4
3 5

输出样例：

2

算法分析

Solution

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range& R) const { return l < R.l; }
} range[N];
int main() {
  int bg, ed;
  cin >> bg >> ed;
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    range[i] = {a, b};
  }
  sort(range, range + n);
  int ans = 0;
  for (int i = 0; i < n;) {
    int j = i, maxR = -2e9;
    while (j < n && range[j].l <= bg) maxR = max(maxR, range[j++].r);//遍历所有相交区间，寻找这些区间的最右端点
    if (maxR < bg) {//最右端点都不能覆盖bg
      cout << -1;
      return 0;
    }
    ans++;
    if (maxR >= ed) {//已经覆盖整个区间
      cout << ans;
      return 0;
    }
    bg = maxR;//更新已覆盖部分的边界
    i = j;//此时j是第一个不相交的区间
  }
  cout << -1;
  return 0;
}