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.

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