本文共 1112 字，大约阅读时间需要 3 分钟。

题目链接:

时/空限制：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 
   
    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;}
   

转载地址：http://aybtf.baihongyu.com/