Here is a challenge for those who want to do some algorithms programming, similar to what you would find in algorithms competitions, such as the IO...
For further actions, you may consider blocking this person and/or reporting abuse
Perl solution, inserting each line into the final array right after having read it. Implementing the binary search myself.
Python
Complexity O(nlog n)
Explanation
The stack contains trips not yet determined to be bad. The trips are processed in ascending
leave_time
. This means any trip already on the stack, has a lower or equalleave_time
than the trip we are currently looking at.If the trip on the top of the stack arrives later than the current trip,
that means the trip on the stack starts earlier and ends later
than the current trip. Therefore the stack trip is worse, and is popped off the stack.
This is repeated until the trip on the top of the stack ends before the current trip.
At that point, all trips down the stack are safe, because
no trip further down the stack ends after the top trip.
After the stack-popping is done, we add the current trip.
If multiple trips start at the same time, the one
with the larger arrive_time comes first, because
it needs to be popped by the better trip, when it comes later.
The sorting we do at the start makes sure
that a trip always comes before the trip it is objectively worse than.
This means the last trip is guaranteed to be good.
Why is
27 40
not part of the solution 2?Ok, there is not an issue with the program, but the test input, rather. The first line says
20
, when there are 30 trips to read. Fixed.That's a very good question! I'll debug my program right after breakfast.
Have you tested on the maximal
N = 1e6
as stated in the problem description? Your solution seems to beO(N*N)
so it will be really slow.One possibility is comparing every pair of trips to see if one is objectively worse than another, but that would take a long time if
N
were the theoretical maximum of 100000.