Snap

[darrenfu]

12/06/2019

• 300. Longest Increasing Subsequence

• Given a pool of airplanes, some are randomly landing, design a taking off sequence strategy.
  Ground rules:

1. Passenger planes are always ahead of Cargo planes.
2. Larger size planes are always ahead of light planes.
3. Planes with longer waiting time on the ground are always ahead of planes with shorter times.

[darrenfu]

intuition for the 2nd question:

1. Heapify all landed planes into two max-heap by plane's size: passenger heap and cargo heap. If some plane lands, push to one of the heap.
2. If two planes are with the same size, store a sub-max-heap as the heap element instead to always have the plane with longest waiting time on the heap top.
3. When we need some plane to take off, always choose passenger heap first; then pop the heap top element, and if there are sub-heap on this element, pop the sub-heap element, which is the plane with longest waiting time.