Greedy Algorithms8 sections · 316 units
Open in Course

Minimum Platforms - Implementation

The code

function findPlatform(arrivals, departures)
 sort arrivals ascending
 sort departures ascending
 platforms := 0
 maxPlatforms := 0
 i := 0
 j := 0
 while i < length of arrivals
 if arrivals[i] <= departures[j] then
 platforms := platforms + 1
 i := i + 1
 else
 platforms := platforms - 1
 j := j + 1
 maxPlatforms := max(maxPlatforms, platforms)
 return maxPlatforms

Time: O(nlogn)O(n \log n). Space: O(1)O(1) extra.