算法基础课题解合集

区间和并

区间合并算法顾名思义，就是快速将区间合并在一起的算法，算法的本质是贪心，下面就来介绍一下此算法的思路。

算法思路

我们首先要把区间按左端点顺序排序，然后分析一下两个区间（假设第一个区间左端点小于等于第二个区间）一共有几种可能的情况。

1. 第一个区间包含第二个区间

这种情况下，我们显然什么都不用干。

2. 两个区间有交错部分

我们可以把第二个区间和第一个区间拼起来，也就是第一个区间的结尾变成第二个区间的结尾。

3. 两个区间没有交集

我们直接把当前处理的区间改成第二个区间即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010;
PII segs[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> segs[i].x >> segs[i].y;
    int st = -2e9, ed = -2e9, res = 0;
    sort(segs, segs + n);
    for (int i = 0; i < n; i ++) {
        if (segs[i].x <= ed) ed = max(ed, segs[i].y);
        else {
            if (st != -2e9) res ++;
            st = segs[i].x, ed = segs[i].y;
        }
    }
    cout << (st == -2e9 ? res : res + 1) << endl;
    return 0;
}

好了，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$