Connection Status:
Competition Arena > RailwayTickets

RailwayTickets

SRM 348 · 2007-05-09 · by soul-net

SRM 348 · 2007-05-09 · by soul-net · Search, Sorting
Class Name: RailwayTickets
Return Type: int
Method Name: minRejects
Arg Types: (vector<string>, int)
Problem Statement

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.

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)
{"2-3 1-4 3-4"}
1
Returns: 1
3)
{"2-3 1-4 3-4 1-3 2-4"}
2
Returns: 2
4)
{"2-3 1-4 3-4 1-3 2-4 1-2"}
2
Returns: 2
5)
{"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.

Submissions are judged against all 115 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RailwayTickets with a public method int minRejects(vector<string> travel, int seats) · 115 test cases · 2 s / 256 MB per case

Submitting as anonymous