21662_PersonnelScheduling

personnel scheduling has been widely studied for many years. The scheduling can be thought of as the problem of assigning employees to shifts or duties over a scheduling period so that certain constraints are satisfied or the assignment achieved some objective.

In this problem, we focus on a basic personnel scheduling system. Suppose there is a small workshop which manufactures accessory for some special tools. This time, the workshop received a series of order forms in a day. Each order form gives out a period of time. For an order form, the workshop owner has to recruit one laborer to manipulate the machine. In this period, other order forms cannot distract the laborer. But when the laborer finished his current work, he can take over another order form.

To minimize the cost, the workshop owner wants to recruit least amount of the laborers. Besides, he has to consider the work-time balance among the laborers — the deviation of the work-time of each laborer should also be minimal. The definition of the deviation D is that, suppose there are m laborers and their work-times are w₁, w₂, ..., w_m, then

Your task is to work out the minimum number of laborers to be recruited and the minimum deviation between these laborers.

The first line of the input gives out the number T ( T ≤ 100 ) of test case. For each test case, the first line is an integer N ( 1 ≤ N ≤ 20 ), representing the number of the order form. The following N lines each line contains two timestamps, "start-time" and "end-time". The format of a time forms "HH:MM" ( 0 ≤ HH < 24,  0 ≤ MM < 60 ). A laborer should be assigned to this period of time, start-time and end-time inclusive.

For each test case, output a line with two number m and D. D is rounded to 2 decimal places.

2
2
01:00 02:00
02:00 02:00
5
00:00 00:00
15:13 15:58
03:38 04:42
03:15 13:56
13:03 21:50

2 0.00
2 47.00