题目描述

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

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

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

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

输入格式
第一行包含整数 n。

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

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

数据范围
1≤n≤100000,
−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

分析

1.有交集时有两种情况：

第一种是第一个区间全包含第二个，如[1,6]和[2, 4];
第二种是两个区间仅有交集，如[1, 6]和[2，8]；第一种情况下，不用动第一个节点，
仅需再从队列，中弹出一个作为第二个，第二种的话需要将第二个节点作为第一个节点，
再弹出一个作为第二个节点。

2.无任何交集时仅一种情况：

如[1, 3]和[4, 6]，这种情况直接将不能合并的第二个区间归队，待第二次操作计数。

C++ 代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1e6 + 10;

typedef struct node
{
    int x, y;

}node;

struct cmp//重载以实现优先队列从小到大的顺序
{
    bool operator()(const node& a, const node& b)
    {
        return a.x > b.x;
    }
};

node a[N]; int n, cnt;//定义结构数组a[N]和计数器cnt

int main()
{
    priority_queue < node, vector <node>, cmp> h;//优先队列，按左区间从小到大排列(左右在一个结构体里)
    cin >> n;

    for (int i = 0; i < n; ++ i) 
    {
        cin >> a[i].x  >> a[i].y;
        h.push(a[i]);
    }

    while (h.size())//如果队头(左区间最小)不为空
    {
        node w = h.top(); h.pop(); //取队头，然后弹出
        ++ cnt;//开始计数
        while (h.size())//如果队头还是不为空
        {
            node v = h.top(); h.pop();//再取队头
            if (w.y >= v.x && w.y < v.y) w = v;//有交集情况中非全包含的情况，需要更新第一个节点
            else if (w.y < v.x) {//无交集情况，将不能合并的区间归队，下一轮取用。
                h.push(v); 
                break;
            }
            //其中有交集，全包含的情况省略了，因为那种情况下什么都不用做。
        }
    }
    cout << cnt <<endl;

    return 0;
}