某些题目对应的智慧数据总结

803. 区间合并

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

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

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

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

输入格式

第一行包含整数 $1\le n\le 10^5$ 。

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

输出格式

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

我二话不说就想了一个，右端点从小到大排序，贪心的写法。

先不说区间输出的时候可能会出现问题，有智慧数据我就是想不出来，对拍才找到，特此记录！

3
2 5
0 3
4 4
----
类似下图
-----
       ---
  -------------
我算法直接就G了。
反过来想，为什么自己就考虑不到这种情况呢？
主要是没有直面自己算法中可能不正确的地方特殊构造！

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int N=1e5+10;
typedef pair<int,int>PII;

int n;
PII a[N];
vector<pair<int,int>>v;
bool cmp(PII a,PII b){
	if(a.second == b.second)return a.first<b.first;
    return a.second<b.second;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i].first,&a[i].second);
    }
    sort(a,a+n,cmp);
    
    int res=1;
    int last = a[0].second;
    int left = a[0].first;
    for(int i=1;i<n;i++){
        if(a[i].first<=last){
            last = a[i].second;
        }
        else{
            v.push_back({left,last});
            res++;
            last = a[i].second;
            left = a[i].first;
        }
    }    
    v.push_back({left,last});
    cout<<res<<endl;
    for(auto c:v){
        cout<<c.first<<" "<<c.second<<endl;
    }
    return 0;
}

在明白了上边的错误之后，果断改成左端点从小到大排序，然后last取max就AC了。

主要是考虑下一条线段可能出现的所有情况。