URAL 1203. Scientific Conference

Author: 2015-08-16

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1203

1203. Scientific Conference

Time limit: 1.0 second
Memory limit: 64 MB
Functioning of a scientific conference is usually divided into several simultaneous sections. For example, there may be a section on parallel computing, a section on visualization, a section on data compression, and so on.
Obviously, simultaneous work of several sections is necessary in order to reduce the time for scientific program of the conference and to have more time for the banquet, tea-drinking, and informal discussions. However, it is possible that interesting reports are given simultaneously at different sections.
A participant has written out the time-table of all the reports which are interesting for him. He asks you to determine the maximal number of reports he will be able to attend.

Input

The first line contains the number 1 ≤ N ≤ 100000 of interesting reports. Each of the next N lines contains two integers Tsand Te separated with a space (1 ≤ Ts < Te ≤ 30000). These numbers are the times a corresponding report starts and ends. Time is measured in minutes from the beginning of the conference.

Output

You should output the maximal number of reports which the participant can attend. The participant can attend no two reports simultaneously and any two reports he attends must be separated by at least one minute. For example, if a report ends at 15, the next report which can be attended must begin at 16 or later.

Sample

input output 
5
3 4
1 5
6 7
4 5
1 3

3

 

2. 思路

给出若干报告会的起止时间，求最多能参加的多少个报告会。

贪心算法。按照报告会结束时间，对报告会列表进行升序排列。排序后的报告会列表中，第一个报告会（最早结束的报告会）一定参加，之后遍历报告会列表，如果后续报告会的开始时间晚于之前所参加报告会的结束时间，则参加该报告会，并进行计数。最后得到所参加的报告会数量，即为所求。

3. 代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_REPORT_NUM 100001

typedef struct ScheduleRecord {
	int start, end;
} Schedule;

void solveE4aScientificConference();
int inputSchedule(Schedule schedule[]);
int cmp(const void *a, const void *b);

int main() {
	solveE4aScientificConference();
	return 0;
}


Schedule schedule[MAX_REPORT_NUM];
void solveE4aScientificConference() {
	int n = inputSchedule(schedule);
	qsort(schedule, n, sizeof(Schedule), cmp);

	int lastEnd = schedule[0].end;
	int cnt = 1;
	for (int i = 1; i < n; ++i) {
		if (schedule[i].start > lastEnd) {
			lastEnd = schedule[i].end;
			++cnt;
		}
	}

	printf("%d\n", cnt);
}

int inputSchedule(Schedule schedule[]) {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		scanf("%d %d", &schedule[i].start, &schedule[i].end);
	}

	return n;
}

int cmp(const void *a, const void *b) {
	return (*(Schedule *)a).end - (*(Schedule *)b).end;
}