Selecting courses HDU - 3697

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 (A _i,B _i). 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 making a try to select a course

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

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<=A _i<B _i<=1000), meaning that the ith course is available during the time interval (Ai,Bi).

The input ends by N = 0.

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

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int v[350];
struct $
{
    int b,e;
} q[350];
bool cmp($ x,$ y)
{
    if(x.e==y.e)
        return x.b<y.b;
    return x.e<y.e;
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        int i,j,k,mm=-90;
        for(i=0; i<n; i++)
            scanf("%d%d",&q[i].b,&q[i].e);
        sort(q,q+n,cmp);
        for(i=0; i<5; i++)
        {
            int c=0;
            memset(v,0,sizeof(v));
            for(j=i; j<=q[n-1].e; j+=5)
            {
                for(k=0; k<n; k++)
                {
                    if(!v[k]&&q[k].b<=j&&q[k].e>j)
                    {
                        c++;
                        v[k]=1;
                        break;
                    }
                }
            }
            mm=max(mm,c);
        }
        printf("%d\n",mm);
    }
    return 0;
}

View Code

Selecting courses HDU - 3697

原文：https://www.cnblogs.com/R-I-P/p/13021756.html