n activities want the same room. Each has a start and a finish time. Find the largest number of activities that can use the room without overlapping. An activity may start exactly when another one finishes.
What to build
A greedy scheduler that picks as many non-overlapping activities as it can.
Requirements
- Read the activities and sort them by finish time, keeping each start with its finish.
- Take the first activity, then each one that starts at or after the finish of the last one taken.
- Print how many were taken.
Input
The first line has n (1 ≤ n ≤ 100). Each of the next n lines has a start and a finish time (0 ≤ start < finish ≤ 10000), in any order.
Output
The largest number of activities.
Constraints
1 ≤ n ≤ 100, and 0 ≤ start < finish ≤ 10000.
Example
Input:
6
1 2
3 4
0 6
5 7
8 9
5 9
Output:
4
Why it works
The activity that finishes first leaves the most room for the others. Any best schedule can swap its first activity for that one and stay valid, so the greedy choice is always safe.
Examples
6 1 2 3 4 0 6 5 7 8 9 5 9
4
3 1 10 2 3 4 5
2
Hints
Hint 1
Sort the activities by finish time (insertion sort on both arrays together is fine for 100 items).
Hint 2
Take the first one; then take each activity whose start is at least the finish of the last one taken.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n;
int start[100], finish[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d %d", &start[i], &finish[i]);
for (int i = 1; i < n; i++) { // insertion sort by finish time
int s = start[i], f = finish[i];
int j = i - 1;
while (j >= 0 && finish[j] > f) {
start[j + 1] = start[j];
finish[j + 1] = finish[j];
j--;
}
start[j + 1] = s;
finish[j + 1] = f;
}
int count = 1, last = 0;
for (int i = 1; i < n; i++) {
if (start[i] >= finish[last]) {
count++;
last = i;
}
}
printf("%d\n", count);
return 0;
}