INPUT FILE: greedy.in
OUTPUT FILE: greedy.out
You have been given the task of scheduling a set of activities; each activity has to take place during a specified period; you will be given the starting and finishing times of each activity. A room can only accomodate one activity at a time, thus any two tasks whose times overlap must be in separate rooms. You are also given an unlimited number of rooms, but you must schedule ALL activites in a MINIMAL number of rooms.
INPUT
The first line will contain an integer k indicating the number of test
cases to follow.
The first line of each test case is an integer n representing the number
of activites in the test case.
On each of the next n lines is the starting and ending time of an activity
to be scheduled.
OUTPUT
For each test case, output the minimum number of rooms needed to accomodate
all of the activites as shown below.
Sample Input File
2 2 0 24 0 1 4 12 13 0 12 23 24 19 23
Output for Sample Input
Minimum number of rooms required is 2. Minimum number of rooms required is 1.