All geek questions in one place

Aircraft planning task since 2009 in the final of ACM-ICPC World Finals

Out of curiosity, I checked the problem posed to the 2009 ACM International Collegiate Programming Contest. The questions are pretty interesting. They are 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. This caused a lively discussion in the office, and we think that we are pretty close to the answer, but we would really appreciate if someone could find / develop a complete solution (no code required).

I will reproduce the problem here for your convenience:

Problem 1

Consider the problem of planning aircraft that land at the airport. Incoming aircraft report their positions, directions and speeds, and then the dispatcher has to develop a landing schedule that safely transfers all planes to the ground. As a rule, the longer the time between successive landings, the “safer” the landing schedule. This extra time gives pilots the opportunity to respond to changing weather and other surprises. Fortunately, part of this planning task can be automated - here you go. You will be given landing scripts. Each aircraft has a time window during which it can land safely. You must calculate the landing order for all aircraft observing these time windows. In addition, aircraft landings should be as long as possible,so that the minimum time interval between successive landings is as large as possible. For example, if three planes land at 10:00, 10:05 and 10:15, the smallest gap is five minutes, which happens between the first two planes. Not all spaces should be the same, but the smallest gap should be as large as possible.

, . , n (2 ≤ n ≤ 8), . n , a i, b i, [a i, b i], i- . a i b i ​​ 0 ≤ a i ≤ b i ≤ 1440, , .

( 1), . , , . .

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


Case 1: 7:30
Case 2: 20:00
+3
4

- :

#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);
    }
}
0

.

( ). , T , . T, , - .

, T, n! , (8! , ). P1... Pn :

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";
+2

Ruby, . , test_case_one , , ( ).

- , . . , .

, , , , :

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 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
0

Source: https://habr.com/ru/post/1724674/

More articles:


All Articles