runway-reservation-scheduler
Source: MIT Lecture 5, Unit 2 : Sorting and trees
Video Resource , Lecture Notes
Runway reservation scheduling is a scheduling problem which needs a data structure for fast insertion and deletion, thus BSTs are best for this type of problem.
Problem Statement:
Design a data structure for a Real life Scenario of a runway reservation system. which should be able to handle :
- Each request will come with a time of landing, on which the plane is suppose to be land.
- Make sure each landing are
k
Minutes away from each other. Call thisK minutes check
.- for example
- If k=3, and there is a landing scheduled in next 5 mins, then there should not be a landing in next 4 mins or 6 mmins (as the k min check will fail).
- for example
- For a given time
t
, show all the landing scheduled fort
and after it. - Each time you delete a node or insert a node, the no. of landings must be managed in recursive calls.