Problem B: 洗衣
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 148 Solved: 26
[Submit][Status][Web Board]
Description
durong有N件衣服要洗， 但是他的第i件衣服必须在[st, en) 时间洗， 同一洗衣机不能同时洗多件衣服，他想，要洗完N件衣服，至少需要多少个洗衣机呢？
Input
多组输入
第一行一个整数n（n <= 100000）, 代表衣服的个数
接下来n行, 每行两个整数st, en（1 <= st < en <= 1000000000），代表第i件衣服在st开始洗，en洗完
Output
输出一个整数和换行符，代表至少需要的洗衣机个数
Sample Input
1 | 3 |
Sample Output
1 | 2 |
贪心，先排序，然后到一个时间点能加就加，如果过了一个减去一个就行了，每次跳跃一件衣服的时间长度就行了，复杂度只有排序的复杂度NlogN
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e5+10;
int n;
int main()
{
` int`st[maxn],en[maxn],sz,ez,ans,cou;
` while`( scanf ( "%d" ,&n)!=EOF)
` {`
` for`( int i=0;i<n;i++){
` scanf`( "%d%d" ,&st[i],&en[i]);
` }`
` sort(st,st+n);`
` sort(en,en+n);`
` ans=cou=ez=0;`
` for`( int i=0;i<n;i++)
` {`
` cou++;`
` while`(en[ez]<=st[i])
` {`
` ez++;`
` cou—;`
` }`
` if`(cou>ans)ans=cou;
` }`
` printf`( "%d\n" ,ans);
` }`
` return`0;
}