时间分隔

Description

Given arrival and departure times of all trains that reach a railway station. Your task is to find the minimum number of platforms required for the railway station so that no train waits.

Note: Consider that all the trains arrive on the same day and leave on the same day. Also, arrival and departure times must not be same for a train.

Input

The first line of input contains T, the number of test cases. For each test case, first line will contain an integer N, the number of trains. Next two lines will consist of N space separated time intervals denoting arrival and departure times respectively.

Note: Time intervals are in the 24-hourformat(hhmm), preceding zeros are insignificant. 200 means 2:00.
Consider the example for better understanding of input.

Constraints:1 <= T <= 100，1 <= N <= 1000，1 <= A[i] < D[i] <= 2359

Output

For each test case, print the minimum number of platforms required for the trains to arrive and depart safely.

Sample Input 1

1
6 
900  940 950  1100 1500 1800
910 1200 1120 1130 1900 2000

Sample Output 1

3

思路

就是求同一时刻，在站台的最大火车数量。把一辆车的到达时间和离开时间看作一个区间，也就是求区间的最大重叠数。

解法：

1. 把每趟火车的到达视为一个到达事件，离开视为一个离开事件

2. 对所有的事件按照时间排序

3. 遍历事件，如果是开始事件，累加器加1；如果是结束事件，累加器减1；

记录遍历过程中累加器的最大值，就是需要的最大站台数量

python (O(n))

def solve(starts, ends):
    events = [(s, 1) for s in starts] + [(e, -1) for e in ends]
    events.sort()
    ans = cur = 0
    for e in events:
        cur += e[1]
        ans = max(ans, cur)
    return ans


for _ in range(int(input())):
    input()
    starts = list(map(int, input().split()))
    ends = list(map(int, input().split()))
    print(solve(starts, ends))