POJ 3697 Selecting courses （贪心）

Selecting courses

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 62768/32768 K (Java/Others)

Total Submission(s): 1291 Accepted Submission(s): 313

Problem Description

A new Semester is coming and students are troubling for selecting courses. Students select their course on the web course system. There are n courses, the ith course is available during the time interval (Ai,Bi). That means, if you want to select the ith course, you must select it after time Ai and before time Bi. Ai and Bi are all in minutes. A student can only try to select a course every 5 minutes, but he can start trying at any time, and try as many times as he wants. For example, if you start trying to select courses at 5 minutes 21 seconds, then you can make other tries at 10 minutes 21 seconds, 15 minutes 21 seconds,20 minutes 21 seconds… and so on. A student can’t select more than one course at the same time. It may happen that no course is available when a student is 易做图 a try to select a course

You are to find the maximum number of courses that a student can select.

Input

There are no more than 100 test cases.

The first line of each test case contains an integer N. N is the number of courses (0<N<=300)

Then N lines follows. Each line contains two integers Ai and Bi (0<=Ai<Bi<=1000), meaning that the ith course is available during the time interval (Ai,Bi).

The input ends by N = 0.

Output

For each test case output a line containing an integer indicating the maximum number of courses that a student can select.

Sample Input

1 10

4 5

Sample Output

Source

2010 Asia Fuzhou Regional Contest

Recommend

chenyongfu

题目大意：有一个人选课，但是不是所有时间都能选，有些课程只在特殊时间段出现，这个人也只会五分钟去尝试一次，问他最多选几门课。

输入输出：输入包含n个数据，接下来n行，即每个课程的出现时间和结束时间，注意是开区间，输出一行，最多选了几门课

解题思路：因为每隔五分钟选一次，所以枚举起始时间就可以了，分别为0.5 , 1.5 , 2.5 , 3.5 , 4.5 就可以了，5.5这个时间点包含在0.5这个起点里面，因为周期是5。

因此起点枚举好了，对于每个起点，整个答案就固定了。如果刚好有一门课，就选了就好了，但是在一次选课时间点中，有多门课怎么办？答案是贪心，选择即将消失的课，因为不选下次一定选不到。

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
  
const int maxn=400;  
  
struct node{  
    int l,r;  
    bool friend operator < (node x,node y){  
        if(x.r!=y.r) return x.r<y.r;  
        else return x.l<y.l;  
    }  
}a[maxn];  
bool visited[maxn];  
  
int n;  
  
void computing(){  
    int ans=0;  
    sort(a,a+n);  
    for(int s=0;s<5;s++){  
        for(int i=0;i<=n;i++) visited[i]=false;  
        int tmp=0;  
        for(int d=s;d<=a[n-1].r;d+=5){  
            for(int t=0;t<n;t++){  
                if(visited[t]) continue;  
                if( d>=a[t].l && d<a[t].r){  
                    visited[t]=true;  
                    tmp++;  
                    break;  
                }  
            }  
        }  
        //cout<<s<<" "<<tmp<<endl;  
        if(tmp>ans) ans=tmp;  
    }  
    cout<<ans<<endl;  
}  
  
int main(){  
    while(scanf("%d",&n)!=EOF && n){  
        for(int i=0;i<n;i++) scanf("%d%d",&a[i].l,&a[i].r);  
        computing();  
    }  
    return 0;  
}

补充：软件开发 , C++ ,