http://acm.nyist.net/JudgeOnline/problem.php?pid=220
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
int sum=0;
int arr[410];
memset(arr,0,sizeof(arr));
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
if(l&1) l++;
if(r&1) r++;
if(l>r)
{
l^=r;
r^=l;
l^=r;
}
for(int j=l;j<=r;j++)
{
arr[j]++;
sum=max(sum,arr[j]);
}
}
printf("%d\n",sum*10);
}
return 0;
}
http://www.scut.edu.cn/oj/ 題號:1924
http://blog.csdn.net/cxllyg/article/details/8200395
假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場平痰。設(shè)計一個有效的貪心算法進(jìn)行安排普筹。(這個問題實際上是著名的圖著色問題寞冯。若將每一個活動作為圖的一個頂點，不相容活動間用邊相連爸邢。使相鄰頂點著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會場數(shù)。)
要求：對于給定的k個待安排的活動宴杀，編程計算使用最少會場的時間表。題解：為了有效地對這n個活動進(jìn)行安排拾因，首先將n個活動區(qū)間的2n個端點排序旺罢。然后旷余，用掃描算法，從左到右掃描整個直線主经。在每個事件點處（即活動的開始時刻或結(jié)束時刻）作會場安排荣暮。當(dāng)遇到一個開始時刻，就將活動安排在一個空閑的會場中罩驻。遇到一個結(jié)束時刻穗酥，就將活動占用的會場釋放到空閑會場棧中，已備使用惠遏。經(jīng)過這樣一遍掃描后砾跃，最多安排了m個會場（m是最大重疊區(qū)間數(shù)）。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<iterator>
using namespace std;
struct point{
int time,flag;
}arr[20010];
int cmp(const void *a,const void * b)
{
return (*(point*)a).time-(*(point*)b).time;
}
int main(){
int n,a;
scanf("%d",&n);
n<<=1;
for(int i=0;i<n;i++)
{
scanf("%d",&a);
arr[i].time=a;
arr[i].flag=i&1;
}
qsort(arr,n,sizeof(point),cmp);
int cnt=0,curr=0;
for(int i=0;i<n;i++)
{
if(arr[i].flag) curr--;
else
{
curr++;
}
if((i==n-1||arr[i].time<arr[i+1].time)&&curr>cnt)
cnt=curr;
/*處理arr[i]==arr[i+1]的情況.當(dāng)cur>cnt且arr[i]==arr[i+1]時节吮，i+1時間可能是開始時間抽高，也可能是
結(jié)束時間。如果i+1是結(jié)束時間透绩，那么i是開始時間,說明某活動開始時間和結(jié)束時間相同翘骂，不需
要會場，故不對cnt更新;如果i+1是開始時間帚豪，那么i是結(jié)束時間,也就是說這兩個事件是可以用同
一個會場的碳竟，那么這兩個時間段可以連在一起當(dāng)作一個時間段，
也就是那在i+1次再更新狸臣，可以看出在i+1次更新cnt效果是一樣的莹桅，因此i次
不進(jìn)行更新。*/
}
printf("%d\n",cnt);
return 0;
}
/**************************************************************
Problem: 1924
User: 201530542552
Language: C++
Result: Accepted
Time:12 ms
Memory:1120 kb
****************************************************************/
