Programming Assessment: Detailed Questions and Answers

4. Implement a Scheduler for Railway Tracks (Greedy + Heap)

Problem:

Design an algorithm to determine the minimum number of railway tracks required to schedule all trains based on their arrival and departure times. Each train needs a track from arrival until departure.

Approach:

Sort all trains by their arrival times.
Use a min-heap to track the earliest departure time of active trains.
Iterate through the sorted list, and for each train:
- If the earliest departure in the heap is less than or equal to the arrival of the current train, reuse the track.
- Otherwise, allocate a new track.
The heap size at any point tells us how many tracks are needed at that time.


import heapq

def min_tracks_required(trains):
    trains.sort()
    heap = []

    for arr, dep in trains:
        if heap and heap[0] <= arr:
            heapq.heappop(heap)
        heapq.heappush(heap, dep)

    return len(heap)

# Example usage
trains = [(100, 200), (150, 300), (180, 250), (400, 500)]
print(min_tracks_required(trains))  # Output: 2

Explanation: This algorithm ensures we’re only adding new tracks when necessary and optimally reuses existing ones.

←→