现在的位置: 首页 > 综合 > 正文

toj2894 Meetings

2014年07月12日 ⁄ 综合 ⁄ 共 754字 ⁄ 字号 评论关闭

题目链接:http://acm.tju.edu.cn/toj/showp2894.html

题目大意:给定一些区间  分别表示会议开始时间和结束时间 问至少要用多少间会议室

思路:贪心  将开始时间和结束时间都按从小到大排序 如果后一个会议的开始时间 大于前一个会议的结束时间 则会议室不用增加;否则,要增加一个会议室。注意下初始化的时候就行 i=0 j=0。(老实说, 就看图就能想出来,没用什么贪心思想,果然还是理解不透彻- -!)

代码:

#include <iostream>
#include <algorithm>
using namespace std;
int s[100006];
int e[100006];
int main()
{
    int t,n,i,j,ans;
    cin>>t;
    while(t--)
    {
       cin>>n;
       for(int j=0;j<n;j++)
          cin>>s[j]>>e[j];
       sort(s,s+n);         //开始时间从小到大排序   
       sort(e,e+n);         //结束时间从小到大排序
       i=0;
       j=0;
       ans=0;
       while(i<n)  //画示意图理解 贪心
       {
          if(s[i]>=e[j])
          {
            i++;
            j++;
          }
          else if(s[i]<e[j])
          {
               i++;
               ans++;
          }
       }
       cout<<ans<<endl;
    }
    return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.