区间和并-

题目一：1399: 校门外的树

P1399 - 校门外的树 - HAUEOJ

代码

#include<bits/stdc++.h>
using namespace std;

using PII = pair<int,int>;
const int N = 1e5+10;
vector<PII>a, b;


int main() {
	int n, m;
	cin >> n >> m;
	while(m --) {
		int l, r;
		cin >> l >> r;
		a.push_back({l,r});
	}
	sort(a.begin(),a.end()); 
	int cnt = n + 1;
	
	int l = -1, r = -1;
	for(int i = 0; i < a.size(); i ++) {
		if(a[i].first>r) {
			if(l!=-1 && r!=-1) 
				b.push_back({l,r});
			l = a[i].first;
			r = a[i].second;
		}
		r = max(r,a[i].second);
	}
	
	b.push_back({l,r}); // 把最后一个区间放进去 
	
	for(auto x : b) {
		cnt -= x.second-x.first+1;
	}

	cout << cnt << endl;
	
	return 0;
}

题目二：1343. 挤牛奶

1343. 挤牛奶 - AcWing题库

代码 

不要忘了sort 左端点，还有处理边界细节，开始0到最前面的左端点不算最长无人持续时间。

#include<bits/stdc++.h>
using namespace std;

int n;
using PII = pair<int,int>;
const int N = 1e4+10;
vector<PII> a, b;

int main() {
    cin >> n;
    while(n --) {
        int l, r;
        cin >> l >> r;
        a.push_back({l,r});
    }
    
    sort(a.begin(),a.end()); // 不要忘了排序左端点
    
    int l=-1, r=-1;
    int maxnotime = 0, maxtime = 0;
    for(int i = 0; i < a.size(); i ++) {
        if(a[i].first>r) {
            //maxnotime = max(maxnotime, a[i].first-r);
            if(l!=-1) {
                b.push_back({l,r});
                maxnotime = max(maxnotime, a[i].first-r);
            }
            l = a[i].first;
            r = a[i].second;
        }
        r = max(r,a[i].second);
    }
    b.push_back({l,r});
    
    for(auto x : b) {
        maxtime = max(maxtime,x.second-x.first);
    }
    
    cout << maxtime << " " << maxnotime << endl;
    return 0;
}

题目三：1400: 现在是摸鱼时间2.0

P1400 - 现在是摸鱼时间2.0 - HAUEOJ

代码 

主要是边界上的考虑。

string 存储端点。PII 存区间

开头st==00：00：00 到第一个区间左端点，第一个需要考虑的边界

末尾st=?max(st,a[i].second) i == a.size()-1, 第二个需要考虑的边界，是否到一天结束

max(st,a[i].second) 是因为要取最右边的，你不知道当前区间右端点是否都比前面的右端点都大，因为排序的是左端点。

#include<bits/stdc++.h>
using namespace std;

// 区间和并，合并重叠的时间
// 除去区间内的区域都摸鱼

using PSS = pair<string,string>;
int n;
vector<PSS> a;

int main() {
	cin >> n;
	while(n --) {
		// string 存储区间端点 
		string s1, s, s2;
		cin >> s1 >> s >> s2;
		a.push_back({s1,s2});
	}
	
	// 排序左端点
	sort(a.begin(),a.end());
	// 边界变量定义 
	string st = "00:00:00";
	int flag = 1; 
	for(int i = 0; i < a.size(); i ++) {
		//开头边界处理 
		if(st=="00:00:00" && a[i].first!="00:00:00") {

			cout << st << " - " << a[i].first << endl;
			st = a[i].second; flag = 0;
			continue;
		}
		
		if(a[i].first<=st) {
			st = max(st,a[i].second);
		}
		else if(a[i].first>st) {
			cout << st << " - " << a[i].first << endl;
			st = a[i].second; flag = 0;
		}
		// 末尾边界处理 
		if(i == a.size()-1 && st<"23:59:59") {
			flag = 0;
			cout << st << " - " << "23:59:59" << endl;
		}
	}
	if(flag) puts("来世还作程序员!");
	return 0;
}