AcWing - 区间合并(贪心)

题目链接:https://www.acwing.com/problem/content/805/
时/空限制：1s / 64MB

题目描述

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式

第一行包含整数n。

接下来n行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000,
−10^9≤li≤ri≤10^9

输入样例

5
1 2
2 4
5 6
7 8
7 9

输出样例

3

解题思路

题意:判断将n个区间可以合并成几个区间。
思路:我们可以先把区间按左端点从小到大排序，先按照第一个区间为标准，即相交区间，判断下一个区间和相交区间是否相交，如果不相交，则从下一个区间重新开始找，否则，就判断该相交区间能不能向右扩展，能的话就扩展，不能就算了，一直这样找就行了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Interval {
    int l, r;
    bool operator < (const Interval &s) const {
        return s.l > l;//按照左端点从小到大排序
    }
}p[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &p[i].l, &p[i].r);
    sort(p, p + n);
    int l = p[0].l, r = p[0].r, cnt = 1;//l, r分别是相交区间的左右端点
    for (int i = 1; i < n; i++) {
        if (r < p[i].l) {//当新的左端点大于相交区间的右端点，则需要更新左右相交端点
            cnt++;
            l = p[i].l, r = p[i].r;//重新更新相交区间
        }
        else if (r < p[i].r)//相交，判断能不能向右扩展
            r = p[i].r;
    }
    printf("%d\n", cnt);
    return 0;
}