Robert Eisele
Engineer, Systems Architect and DBA

Skillvalue: 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.

InputN > 0 integer – number of planes and A[N] and D[N] representing the hours of arrival and departure.

OutputG – number of gates.

ExampleFor 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.

TimeTypeGates
9:00Arrival1
9:10Departure0
9:40Arrival1
9:50Arrival2
11:00Arrival3
11:20Departure2
11:30Departure1
12:00Departure0
15:00Arrival1
18:00Arrival2
19:00Departure1
20:00Departure0

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(' ') })

« Back to problem overview