John is writing a program that finds the best route from A to B using public transport. For a given pair of origin and destination the program calculates a set of routes with departure time and arrival time, such as this:
10:12 11:45 10:15 11:50 10:22 12:05 10:25 12:00
As you see, the output may include a few routes that are superfluous in the sense that there is another route that starts later and ends earlier. Such routes are certainly never wanted by the user since he cat get out later to arrive sooner.
Your task, if you choose to accept it, is to write a program that prunes a set of routes such that all superfluous rules are eliminated.
The input is a list of newline separated pairs of whitespace separated departure and arrival time in military format (hh:mm). Such a pair is called a route.
You may assume that all times are in the same day and that the arrival time is always later than the departure time. You may also assume that the list is orderer by departure times.
The output is the same list as the input without redundant routes. A redundant route is a route for which another route exists in the list that has a later departure and an earlier arrival time. There must exist an order to remove all redundant routes such that in each step you can show the route that makes the removed route redundant. You don't have to output that order.
Prove or disprove that for each list of input routes there exists exactly one set of output routes.
- Usual codegolf rules apply
To score, apply the function that gives an upper bound to your solutions complexity with your solution's total number of characters. Normalize your bounding function such that a solution length of two character yields a score of two.
For example, if your solution has 24 characters and a complexity of O(2n), your score is 4194304. If your solution has 123 characters and a complexity of O(n2) your score is 7564. If your solution has 200 characters and a complexity of O(n*logn), your score is 734.
I use this scoring method in order to encourage people to implement efficient solutions.