1488 . KTX Train Depot
Description
KTX (Korea Train eXpress), Korea's high-speed rail system operated by KORAIL, connects the capital Seoul to several major cities of the Korean Peninsula. KORAIL's most recent train sets KTX-II, which were developed in Korea, can travel at over 350 km/h. The next-generation test train is currently being developed, and the train is planned to be able to travel at over 400 km/h by 2012. KTX Goyang Train Depot, which is located behind Haengsin Station, is one of the biggest train depots in Korea. The train depot consists of a set of parallel tracks for storing KTX trains and facilities for carrying out repair jobs.
All trains whose home is KTX Goyang Train Depot enter the depot until the middle of the night and leave it in the morning. Each train might enter the depot either from the eastern side or from the western side and might leave the depot to the eastern side or to the western side. The direction from which it enters or to which it leaves the depot, however, is fixed. Also the arrival and departure times are fixed. Hence, the train is labeled with the time interval [t1, t2] in which it stays in the depot and an arrival and departure direction d1 and d2, respectively. For example, a train labeled [-6E,13W] is a train that enters the depot at time -6 from the eastern side and leaves the depot at time 13 to the western side. In the meanwhile, it stops on one of several parallel tracks in the depot.
No two trains arrive from the same direction at the same time or depart to the same direction at the same time. There might be several trains waiting at the same track. Each train is assigned to a track such that it can leave the depot on time without being blocked by other trains. That is, the assignment of Figure 1 is not feasible, since train [-2E,2W] would be blocked by train [-1W,4W]. The assignments in Figures 2(a) and 2(b) are both feasible. However, an interesting assignment is the one in Figure 2(b), which uses the minimum number of tracks.
It is planned to increase the number of KTX trains whose home is KTX Goyang Train Depot. Dr. Chwa, who is the President of KORAIL Research Institute, foresees that it might cause a difficulty in storing trains in the depot due to the limit on the number of tracks. The length of a track will be no problem since each track is long enough to store even all the trains. Dr. Chwa is eager to determine the minimum number of tracks to store all the trains such that each train can leave the depot on time without being blocked by other trains. Write a program that can help him.
Input Format
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains an integer n which represents the number of trains, where 1 <= n <= 10,000. In the following n lines, each line contains a train label t1d1t2d2, which represents a train that enters the depot at time t1 from the direction d1 and leaves the depot at time t2 to the direction d2, where t1 and t2 are integers such that - 1,000,000 <= t1 < 0 < t2 <= 1,000,000 and d1, d2 ∈ {E,W}. Every line of the input contains no whitespaces except the newline character.
Output Format
Your program is to write to standard output. Print exactly one line for each test case that contains an integer representing the minimum number of tracks that Dr. Chwa is eager to know.
The following shows sample input and output for three test cases.
Sample Input 1
3 4 -4E1W -3E3E -1W4W -2E2W 3 -3E9W -2E8W -1E7W 3 -3E9E -2W8W -1W7W
Sample Output 1
2 3 1
Hints
Problem Source
Migrated from old NTUJ.
ACM ICPC 2010 Daejeon regional
Subtasks
| No. | Testdata Range | Score |
|---|