题目描述

代码

#include<bits/stdc++.h>
using namespace std;
class worker{
	public:
		int start;
		int end;
		worker(){
			
		}
		worker(int a, int b){
			start = a; end = b;
		}
};

bool cmp(worker w1, worker w2){
	return w1.start < w2.start;
}
int main(){
	int N;
	cin>>N;
	vector<worker> workers;
//	vector<int> start;
//	vector<int> end;
	int n = N;
	while(n--){
		int a,b;
		cin>>a>>b;
		worker w(a,b);
		workers.push_back(w);
	} 
	sort(workers.begin(), workers.end(), cmp);
	
//	for(int i = 0; i < N; i++){
//		cout<<workers[i].start<<" "<<workers[i].end<<endl;
//	}
	
	int left,right;
	left = workers[0].start; right = workers[0].end;
	int MAX = right - left;
	int gap = 0;
	
	for(int i = 1; i < N; i++){
		if(workers[i].start <= right){
			right = max(right, workers[i].end );
			MAX = max(right - left,MAX);//这里 
		}else{
			gap = max(workers[i].start - right, gap);
			left = workers[i].start;
			right = max(right, workers[i].end);
			MAX = max(right - left, MAX);
		}
	}
	cout<<MAX<<" "<<gap;
	return 0;
}

贴一下我参考的题解：
https://www.cnblogs.com/wafish/p/10465503.html
这道题是一道贪心，在算法上并不太难，但是在代码实现上很麻烦。
首先，在应用贪心之前需要定义结构体或类来存储工人的起止时间，然后对工人的数据按起始时间进行升序排列，创造使用贪心的条件，不然的话你会发现如果在遍历过程中起始时间一会往前一会往后，根本没办法用贪心。
第二个难点就是遍历过程中的操作。

int left,right;
	left = workers[0].start; right = workers[0].end;
	int MAX = right - left;
	int gap = 0;
	
	for(int i = 1; i < N; i++){
		if(workers[i].start <= right){
			right = max(right, workers[i].end );
			MAX = max(right - left,MAX);//这里 
		}else{
			gap = max(workers[i].start - right, gap);
			left = workers[i].start;
			right = max(right, workers[i].end);
			MAX = max(right - left, MAX);
		}
	}

我刚开始犯的一个错误就是理解错了题意，gap指的是从第一个工人开始工作的间隔，而不是从6:00开始的间隔，所以gap应该初始化为0
另外，当遇到断层时，left和right需要重新开始计算，但是MAX不一定，因为最长连续工作时间不一定会更新，所以无论有没有出现断层，都要有MAX = max(right - left,MAX);
以后如果遇到思路很清楚没问题，但是答案一直错误的情况，需要停下来尽量想一想样例中有没有漏掉的特殊情况，然后再想一想是不是对整个代码的执行过程有误解，最好把不同的情况都在纸上演练一遍。