挤牛奶

题目描述

三个农民每天清晨 5 点起床，然后去牛棚给三头牛挤奶。

第一个农民在 300 秒 (从 5 点开始计时) 给他的牛挤奶，一直到 1000 秒。第二个农民在 700 秒开始，在 1200 秒结束。第三个农民在 1500 秒开始，2100 秒结束。

期间最长的至少有一个农民在挤奶的连续时间为 900 秒 (从 300 秒到 1200 秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为 300 秒 (从 1200 秒到 1500 秒)。

你的任务是编一个程序，读入一个有 n 个农民挤 n 头牛的工作时间列表，计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段。

最长的无人挤奶的时间段。（从有人挤奶开始算起）
输入格式

第一行一个正整数 n

接下来 n 行，每行两个非负整数 l,r，表示一个农民的开始时刻与结束时刻。
输出格式

一行，两个整数，即题目所要求的两个答案。
输入输出样例
输入 #1

3
300 1000
700 1200
1500 2100

输出 #1

900 300

说明/提示

【数据范围】
对于 100% 的数据，1≤n≤5000，0≤l≤r≤106。

题目分析

有n个时间段，n个人，每个时间段都已一人挤奶（可能同时进行），每次挤奶有一人从li挤到ri，问最大有人挤奶时间段和无人挤奶时间段

解题思路

这题我们可以用离散化，用一个结构体去找答案就OK了
离散化题目

AC代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,s,ss;
struct node
{
   
	int head,tail;
}a[5005],x;
bool cmp(node x,node y)//快排
{
   
	if(x.head==y.head)return x.tail<y.tail;
	return x.head<y.head;
}
int main()
{
   
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 scanf("%d%d",&a[i].head,&a[i].tail);	
	sort(a+1,a+n+1,cmp);//快排
	x.head=a[1].head;//用一个x存头尾
	x.tail=a[1].tail;
	s=a[1].tail-a[1].head;//s为工作时间
	for(int i=2;i<=n;i++)
	{
   
		if(a[i].head<=x.tail)x.tail=max(a[i].tail,x.tail);//如果当前的头包含在上一个的尾中，就判断当前的尾和上一个的尾谁大，如果当前的尾大，就更新x.tail，否则不变
		else//如果没有包含
		{
   
			s=max(s,x.tail-x.head);//max工作时间
			ss=max(ss,a[i].head-x.tail);//max未工作时间
			x.head=a[i].head;//赋值
			x.tail=a[i].tail;
		}
	}
	printf("%d %d",s,ss);
}

谢谢