AcWing 803. 区间合并

# 区间合并 - 贪心

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int>PII;

const int N = 1e6 + 10;

int n;
vector<PII> segs;

void merge(vector<PII> &segs){
	vector<PII> res;
	sort(segs.begin(), segs.end());
	int st = -2e9, ed = -2e9;
	for(auto seg : segs)
		if(ed < seg.first){
			if(st != -2e9) res.push_back({st, ed});
			st = seg.first, ed = seg.second;
		}
		else ed = max(ed, seg.second);
	if(st != -2e9) res.push_back({st, ed});
	segs =res;
}
int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		int l, r;
		cin >> l >> r;
		segs.push_back({l, r});
	}
	merge(segs);
	cout << segs.size() << endl;
	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n;
vector<PII> segs;

void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
    //如果没交集就加载进result
        if(ed < seg.first){
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        //否则就是有交集 就是求两个区间的并集
        //1.更新成维护的区间
        //2.更新成当前区间的右端点的最大值 因为sort了 所以不可能左端点更新
        else ed = max(ed, seg.second);
       
    //把最后更新完的区间加到result里去 
    if(st != -2e9) res.push_back({st, ed});
    //!=这个判断是防止我们输入里面是没有任何区间的
    
    segs = res;
    //把segs 更新成result
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
    
    
    return 0;
}