Co-ordinating flights

Computer Science Level 5

Apparently the three flight terminals in Mathiland are disorganized and supposed to have two planes on the same runway now but that's obviously not going to happen. Your job is to fix to flight disorganization. This file contains a list of the flights and their time of departure in 24 hour time (23:45, 13:59, etc.). You have the option to move the departure times forward or backwards by a maximum of five minutes and the time taken for an airplane to take off and have the runway clear again is 20 minutes. If the runway is occupied 5 minutes before until 5 minutes after the expected takeoff time, the flight will be cancelled.

Given the list, find the maximum number of planes that can take off in that day.

Assumptions

We only have one run way.
All of these happen in the same day.

Image credit: Wikipedia Terence Ong

The answer is 19.

1 solution

Daniel Lim
Aug 4, 2014

This problem is quite nice, my code didn't solve the problem on my first try, so since the amount of flights is so small, I decided to use brute-force to search for the answer, and I got it right, but I still tried to fix the bug in my code, and here it is:

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

pair<int, int> parse(string time){
    int hr, min;
    hr = (time[0] - '0') * 10 + (time[1] - '0');
    min = (time[3] - '0') * 10 + (time[4] - '0');
    pair <int, int> t;
    t.first = hr;
    t.second = min;

    return t;
}

void addTime(pair<int, int> &time, int mins){
    time.second += mins;
    if (time.second >= 60){
        time.second -= 60;
        time.first += 1;
    }
    if (time.second < 0){
        time.second += 60;
        time.first -= 1;
    }
}

int timeDifference(pair<int, int> time1, pair<int, int> time2){
    int t1, t2;
    t1 = time1.first * 60 + time1.second;
    t2 = time2.first * 60 + time2.second;

    return t2 - t1;
}

int main(){

    freopen("flights.txt", "r", stdin);
    freopen("answer.txt", "w", stdout);

    vector <pair <int, int> > times(24);
    for (int i = 0; i < 24; i++){
        string time; cin >> time;
        times[i] = parse(time);
    }

    sort(times.begin(), times.end());

    int ans = 0;
    vector <bool> available(24);
    for (int i = 0; i < 24; i++){
        available[i] = true;
    }

    for (int i = 0; i < 24; i++){
        if (!available[i])
            continue;

        if (i == 23 && available[i]){
            ans++;
            break;
        }

        addTime(times[i], 20);

        int dt = timeDifference(times[i], times[i + 1]);

        if (dt > 0){
            ans++; 
            continue;
        }

        if (i > 0){
            int tmp = timeDifference(times[i - 1], times[i]);

            if (tmp > 0){
                if (tmp > 5){
                    addTime(times[i], -5);
                }
                else
                    addTime(times[i], -tmp + 1);
            }
        }

        dt = timeDifference(times[i], times[i + 1]);

        if (dt > 0){
            ans++; 
            continue;
        }
        else{
            int tmp = timeDifference(times[i], times[i + 1]);
            tmp -= 20;
            if (tmp > 0){
                if (tmp > 5)
                    addTime(times[i + 1], 5);
                else
                    addTime(times[i + 1], tmp - 1);
            }

        }

        if (dt <= 0)
            available[i + 1] = false;

        ans++;
    }

    cout << ans;

    return 0;
}

I will explain my code.

First, I read all inputs and parse it into my desired format. Then, I sorted them. After sorting, I initialized an array(should be vector) of boolean values to true(I will explain why I do this later), and initialize the variable ans to 0.

Here's what I do next to find the answer:

Check if the flight is available.
Find the time difference and check if it does not overlap the next flight. If it doesn't, add 1 to ans and proceed to the next flight.
Then, I try to move the time forward as many as I can.
Check again if the flight does not overlap the next flight. If doesn't, do the same thing as 2.
Then, I try to delay the flight as far as I can.
Now, check if they overlap. If they overlap, we have no choice but to cancel the next flight.
Add 1 to ans.

If you have any problems with my code, please let me know.

Actually it could be done by Greedy Algrorithm, this is similar to Interval scheduling And there is my code (so few data, so python it is)

flight_time = lambda x: int(x.split(":")[0])*60+int(x.split(":")[1])
start = lambda x: x-5
end = lambda x: x+20
overlap = lambda this, that: (end(this)>that and this<that)
get_time = lambda x: str(x/60).zfill(2)+":"+str(x%60).zfill(2)

def read_data(filename):
    f = open(filename)
    times = [flight_time(line.strip()) for line in f]
    return times

def flight_can_takeover(times):
    times = sorted(times)
    last_time = times[0]
    count = 1
    feasible_time = [get_time(last_time)]
    for t in times:
        if (not overlap(last_time, t)):
            count+=1
            last_time = max(end(last_time),start(t))
            feasible_time.append(get_time(last_time))
    return feasible_time

if __name__ == '__main__':
    times = read_data("co-ordinateing.txt")
    feasible_times = flight_can_takeover(times)
    print len(feasible_times)

I used a file and the code flows like this:

read the data, and convert them into int
sort them in the increasing order
iterate through the time, update the last feasible time, and counter if a new feasible time found

Dingcheng Yue - 6 years, 10 months ago

Co-ordinating flights

Image credit: Wikipedia Terence Ong

The answer is 19.

1 solution

0 pending reports