Can you answer this 2009 ACM International Collegiate Programming Contest Finals problem?

Question

Out of curiosity, I was checking out the problem set to the 2009 ACM international collegiate programming contest. The questions are pretty interesting. They're available at http://cm.baylor.edu/resources/pdf/2009Problems.pdf. I could not come up with an algorithm that solved problem 1, which I will reproduce here. It set off a lively discussion in the office, and we think we're pretty close to an answer, but we'd really appreciate it if somebody could find/work out a full solution (code not required).

I will reproduce problem here for your convenience:

Problem 1

Consider the task of scheduling the airplanes that are landing at an airport. Incoming airplanes report their positions, directions, and speeds, and then the controller has to devise a landing schedule that brings all airplanes safely to the ground. Generally, the more time there is between successive landings, the “safer” a landing schedule is. This extra time gives pilots the opportunity to react to changing weather and other surprises. Luckily, part of this scheduling task can be automated – this is where you come in. You will be given scenarios of airplane landings. Each airplane has a time window during which it can safely land. You must compute an order for landing all airplanes that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible. For example, if three airplanes land at 10:00am, 10:05am, and 10:15am, then the smallest gap is five minutes, which occurs between the first two airplanes. Not all gaps have to be the same, but the smallest gap should be as large as possible.

Input

The input file contains several test cases consisting of descriptions of landing scenarios. Each test case starts with a line containing a single integer n (2 ≤ n ≤ 8), which is the number of airplanes in the scenario. This is followed by n lines, each containing two integers ai, bi, which give the beginning and end of the closed interval [ai, bi] during which the ith plane can land safely. The numbers ai and bi are specified in minutes and satisfy 0 ≤ ai ≤ bi ≤ 1440. The input is terminated with a line containing the single integer zero.

Output

For each test case in the input, print its case number (starting with 1) followed by the minimum achievable time gap between successive landings. Print the time split into minutes and seconds, rounded to the closest second. Follow the format of the sample output.

Sample Input

3
0 10
5 15
10 15
2
0 10
10 20
0

Sample Output

Case 1: 7:30
Case 2: 20:00

Answer 1

I would do something like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef uint MASK;
#define INPUT_SCALE 60
#define MAX_TIME (1440 * 60)


void readPlaneData(int& endTime, MASK landingMask[MAX_TIME], int index)
{
    char buf[128];
    gets(buf);
    int start, end;
    sscanf(buf, "%d %d", &start, &end);

    for(int i=start * INPUT_SCALE; i<=end * INPUT_SCALE; i++)
     landingMask[i] |= 1 << index;

    if(end * INPUT_SCALE > endTime)
     endTime = end * INPUT_SCALE;
}


int findNextLandingForPlane(MASK landingMask[MAX_TIME], int start, int index)
{
    while(start < MAX_TIME)
    {
     if(landingMask[start] & (1 << index))
      return start;
     start++;
    }

    return -1;
}


bool canLandPlanes(int minTime, MASK landingMask[MAX_TIME], int planeCount)
{
    int next = 0;
    for(int i=0; i<planeCount; i++)
    {
     int nextForPlane = findNextLandingForPlane(landingMask, next, i);
     if(nextForPlane == -1)
      return false;

     next = nextForPlane + minTime;
    }

    return true;
}


int main(int argc, char* argv[])
{
    while(true)
    {
     char buf[128];
     gets(buf);
     int count = atoi(buf);
     if(count == 0)
      break;

     MASK landingMask[MAX_TIME];
     memset(landingMask, 0, sizeof(landingMask));

     int endTime = 0;
     for(int i=0; i<count; i++)
      readPlaneData(endTime, landingMask, i);

     while((endTime > 0) && !canLandPlanes(endTime, landingMask, count))
      endTime--;

     printf("%d:%02d\n", endTime / 60, endTime % 60);
    }
}

Answer 2

This optimization problem can be solved by linear programming http://en.wikipedia.org/wiki/Linear_programming

Answer 3

I'll give a sketch of the algorithm.

First you binary search through the answer (minimal interval between flights). To do that, for each selected interval T you must be able to check whether it is possible to achieve it. If it is possible to achieve T, then you try making it smaller, if it is not - make it bigger.

To check whether you can achieve T, try all n! orders in which the planes may be landing (8! is small enough for this algo to work in time). For each permutation P1...Pn, you try assigning the times in a greedy manner:

int land = a[0];
for (int i = 1; i < n; i++) {
    land = max(a[i], land + **T**);
    if (land > b[i]) return "CAN NOT ACHIEVE INTERVAL T";
}
return "CAN ACHIEVE";

Answer 4

Here's some Ruby code that brute-forces the solution. Note that test_case_one actually fails because I have commented out the code that would make this work with seconds (instead of just whole minutes).

The brute-force strategy is to permute all the sequences in which the planes may land. For each landing sequence, create the product of all possible landing times. This is fine with whole minutes, brutal with seconds.

But of course premature optimization, evil, and all that, so this is a first step:

require 'test/unit'

class SampleTests < Test::Unit::TestCase
  def test_case_one
    problem = Problem.new
    problem.add_plane(Plane.new(0, 10))
    problem.add_plane(Plane.new(5, 15))
    problem.add_plane(Plane.new(10, 15))
    problem.solve()
    minimum_gap = problem.minimum_gap()
    assert_equal(7.5, minimum_gap)
  end

  def test_case_two
    problem = Problem.new
    problem.add_plane(Plane.new(0,10))
    problem.add_plane(Plane.new(10, 20))
    problem.solve()
    minimum_gap = problem.minimum_gap()
    assert_equal(20, minimum_gap)
  end

  def test_case_three
    problem = Problem.new
    problem.add_plane(Plane.new(0, 2))
    problem.add_plane(Plane.new(7, 10))
    problem.add_plane(Plane.new(4, 6))
    minimum_gap = problem.minimum_gap()
    assert_equal(5, minimum_gap)
  end

  def test_case_four
    problem = Problem.new
    problem.add_plane(Plane.new(1439, 1440))
    problem.add_plane(Plane.new(1439, 1440))
    problem.add_plane(Plane.new(1439, 1440))
    assert_equal(0, problem.minimum_gap())
  end

  def test_case_five
    problem = Problem.new
    problem.add_plane(Plane.new(0, 10))
    problem.add_plane(Plane.new(1, 2))
    assert_equal(9, problem.minimum_gap())
  end

  def test_case_six
    problem = Problem.new
    problem.add_plane(Plane.new(8, 9))
    problem.add_plane(Plane.new(0, 10))
    assert_equal(9, problem.minimum_gap())
  end
end

class Plane
  def initialize(min, max)
    @ts = Array.new
    #This is a cheat to prevent combinatorial explosion. Just ignore 60 seconds in a minute!
    #min = min * 60
    #max = max * 60
    min.upto(max) { | t | @ts << t}
  end

  #Array of times at which the plane might land. 
  def times
    return @ts
  end
end

#from 'permutation' gem
class Array
  def permute(prefixed=[])
      if (length < 2)
          # there are no elements left to permute
          yield(prefixed + self)
      else
          # recursively permute the remaining elements
          each_with_index do |e, i|
              (self[0,i]+self[(i+1)..-1]).permute(prefixed+[e]) { |a| yield a }
          end
      end
  end
end


class Problem
  def initialize
    @solved = false
    @maximum_gap = 0
    @planes = Array.new
  end

  def add_plane(plane)
    @planes << plane
  end

  #given a particular landing schedule, what's the minimum gap?
  #A: Sort schedule and spin through it, looking for the min diff

  #Note that this will return 0 for invalid schedules (planes landing simultaneously)
  def gap_for(schedule)
    schedule.sort!
    min_gap = 1440
    0.upto(schedule.length - 2) { | i |
      gap = schedule[i + 1] - schedule[i]
      if gap < min_gap
        min_gap = gap
      end 
    }
    return min_gap
  end

  #Brute-force strategy
  #Get every possible plane sequence (permute)
  #Get every possible schedule for that sequence (brute_force_schedule)
  #Check that schedule
  def solve
    @planes.permute { | sequence |
        schedules = brute_force_schedule(sequence)
        schedules.each { | schedule | 
          schedule.flatten!
          gap = gap_for(schedule)
          if gap > @maximum_gap
              #puts "Found a new one: #{schedule.inspect}"
              @maximum_gap = gap
          end
        }
    }
  end

  #The list of all possible schedules associated with an array of planes
  def brute_force_schedule(planes)
    head = planes[0]
    tail = planes[1..-1]
    if tail.empty?
      #Last element, return the times
      return head.times.to_a
    else
      #Recurse and combine (product) 
      return head.times.to_a.product(brute_force_schedule(tail))
    end
  end


  def minimum_gap
    unless @solved
      solve
    end
    return @maximum_gap
  end
end