Heap Algorithmic Issue
- by OberynMarDELL
I am having this algorithmic problem that I want to discuss about. Its not
about find a solution but about optimization in terms of runtime. So here it is:
Suppose we have a race court of Length L and a total of N cars that participate
on the race. The race rules are simple. Once a car overtakes an other car the second
car is eliminated from the race. The race ends when no more overtakes are possible
to happen.
The tricky part is that the k'th car has a starting point x[k] and a
velocity v[k]. The points are given in an ascending order, but the velocities
may differ.
What I've done so far:
Given that a car can get overtaken only by its previous, I calculated the time
that it takes for each car to reach its next one
t = (x[i] - x[i+1])/(v[i] - v[i+1])
and I insert these times onto a min heap in O(n log n).
So in theory I have to pop the first element in O(logn), find its previous,
pop it as well , update its time and insert it in the heap once more, much
like a priority queue. My main problem is how I can access specific points of a
heap in O(log n) or faster in order to keep the complexity in O(n log n) levels.
This program should be written on Haskell so I would like to keep things simple
as far as possible
EDIT: I Forgot to write the actual point of the race. The goal is to find the order in which cars exit the game
