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.
|