Skillvalue Solution: Minimum Gates
Given an airport with the arrival and departure times of all planes that are scheduled for taking off and landing.
Find the minimum number of gates required for the airport to function.
You are given two arrays which represent arrival and departure times of the planes.
Input: N > 0 integer – number of planes and A[N] and D[N] representing the hours of arrival and departure.
Output: G – number of gates.
Example: For the following input:
N = 6
A[] = [9:00, 9:40, 9:50, 11:00, 15:00, 18:00]
D[] = [9:10, 12:00, 11:20, 11:30, 19:00, 20:00]
Output is 3.
Solution
When we order the two arrays in ascending order by time it becomes obvious that we can increment or decrement the number of gates by event type - either arrival or departure. Based on that we can maximize the number of gates, which will become the minimum number of necessary gates.
| Time | Type | Gates |
|---|---|---|
| 9:00 | Arrival | 1 |
| 9:10 | Departure | 0 |
| 9:40 | Arrival | 1 |
| 9:50 | Arrival | 2 |
| 11:00 | Arrival | 3 |
| 11:20 | Departure | 2 |
| 11:30 | Departure | 1 |
| 12:00 | Departure | 0 |
| 15:00 | Arrival | 1 |
| 18:00 | Arrival | 2 |
| 19:00 | Departure | 1 |
| 20:00 | Departure | 0 |
Implementing this idea can then look like the following Ruby snippet:
def parse(t)
d = t.split(":").map(&:to_i)
d[0] * 60 + d[1]
end
def minimum_gates(arrivals, departures)
c = 1
max = 1
i = 1
j = 0
while i < arrivals.length and j < departures.length
if parse(arrivals[i]) <= parse(departures[j])
i+= 1
c+= 1
max = c if c > max
else
j+= 1
c-= 1
end
end
max
end
puts minimum_gates(*File.readlines(ARGV[0]).map(&:chomp).map { |l| l.split(' ') })