TopCoder problem "RailwayTickets" used in SRM 348 (Division I Level Two)



Problem Statement

    

A railway company has a special train line that goes through an unshared rail, passing by several stations along the way. Stations are numbered increasingly in the direction the train passes them (the train is only one-way). Each client must schedule his trip (indicating departing and arriving stations) at least a day before it is made. Your task is to write a program that determines the minimum number of requests that must be denied in order to ensure that everybody gets a seat.

You will be given an int seats which indicates the maximum number of passengers that can be inside the train at the same time. You will also be given the list of requests as a String[] travel. Each element of travel will be a single space separated list of requests of the form "A-B" (quotes for clarity), where A is the departing station and B is the arriving station. You must decide whether each request should be accepted or denied. Accepted requests will be assigned a seat number, and no two passengers whose trips overlap can have the same seat. Return the minimum number of requests you must deny in order to fulfill the above requirements.

 

Definition

    
Class:RailwayTickets
Method:minRejects
Parameters:String[], int
Returns:int
Method signature:int minRejects(String[] travel, int seats)
(be sure your method is public)
    
 

Constraints

-seats will be between 1 and 1000, inclusive.
-travel will contain between 1 and 50 elements, inclusive.
-Each element of travel will contain between 1 and 50 characters, inclusive.
-Each element of travel will be a single space separated list, with no leading or trailing spaces, of requests of the form "A-B" (quotes for clarity) where A and B are integers between 1 and 10000, inclusive, with no leading zeroes, and A is strictly less than B.
 

Examples

0)
    
{"1-3 3-5",
 "2-4 4-6",
 "1-2 2-3 3-4 4-5"}
2
Returns: 2
There are only 2 seats in the train, so you must surely get 1-3, 2-4 or 2-3 out, because they all won't fit during the travel from station 2 to station 3. Also, one of 3-5, 4-6 or 4-5 has to go. Eliminating only 2-4 and 4-6 leaves enough room for the rest (assigning seat 1 to 1-3 and 3-5 and seat 2 to 1-2, 2-3, 3-4 and 4-5).
1)
    
{"1-10000","2-10000","1-9999","2-9999","5000-5001"}
3
Returns: 2
Two people cannot share the same seat, so we can only accommodate 3 of these requests.
2)
    
{"1-2 2-5 2-8 234-236 56-878 6-34",
 "234-776 3242-8000 999-1000 3-14",
 "121-122 435-3455 123-987 77-999"}
1000
Returns: 0
There's plenty of room for everybody.
3)
    
{"1-2 2-3 3-4 4-5 5-6 6-7 1-3 2-7 1-2 1-4"}
1
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7760

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10672&pm=7760

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Search, Sorting