How would it be possible to make this code run faster in C . The code takes a lot of time to run. The purpose is to determine how many gates are required to handle a prescribed arrivals-and-departures schedule.

#include <vector>

struct Airplane {
    int arrival_time_seconds;
    int departure_time_seconds;
};

class Schedule {
private:
    const std::vector<Airplane> airplanes_;

public:
    Schedule(const std::vector<Airplane>& airplanes) :
        airplanes_(airplanes) {}

    int MaximumNumberOfPlanes() const {
        int rv = 0;
        for (const Airplane& airplane : airplanes_) {
            int num_planes = NumberOfPlanes(airplane.arrival_time_seconds);
            if (num_planes > rv) {
                rv = num_planes;
            }
        }
        return rv;
    }

private:
    int NumberOfPlanes(int time_seconds) const {
        int rv = 0;
        for (const Airplane& airplane : airplanes_) {
            if (airplane.arrival_time_seconds < time_seconds &&
                    time_seconds <= airplane.departure_time_seconds) {
                rv  ;
            }
        }
        return rv;
    }
};

CodePudding user response：

The algorithm is written as an O(N²) problem but it can be easily rewritten as an O(N) problem.

First you need to order the vector of airplanes by arrival time so the vector is a (duh) sorted sequence. Every time you add a new airplane you have to insert it in order. You could even think about using std::map as a container instead.

Then you go walking forward on the "current" airplane while keeping a pointer to the first airplane. The difference of the two is your current number of airplanes parked.

Once you increment your index, you check if the departure time of the "last" airplane is smaller than the new current time. If so you increment.

That should be extremely fast.

CodePudding user response：

A lot of people stated that this can be made O(N), and it is possible to some extent. At least I was able to make it O(max(N,86400)) which is better than your version for N>294 and better than a O(NlogN) for N>6788.

I assume that if a plane departs the next day it has a departure_time_seconds = 86400 (the number of seconds in a day), while all arrival_time_seconds are lower than 86400.

You can compile a vector of the change in number of planes in O(N) and than use it to compute the current number of planes in the airport at every second in O(86400):

    int MaximumNumberOfPlanes2() const {
        int delta[24 * 60 * 60   1] = { 0 };
        for (const Airplane& x : airplanes_) {
            delta[x.arrival_time_seconds]  ;
            delta[x.departure_time_seconds]--;
        }
        int rv = 0;
        int np = 0;
        for (int i = 0; i < 24 * 60 * 60;   i) {
            np  = delta[i];
            rv = std::max(rv, np);
        }
        return rv;
    }

A test program with some timing:

#include <vector>
#include <iostream>
#include <fstream>
#include <random>
#include <chrono>
#include <queue>

int main()
{
    using namespace std;
    using namespace std::chrono;

    default_random_engine eng;
    uniform_int_distribution<int> arr_dist(0, 24*60*60);
    gamma_distribution<double> dep_dist(5, 3);

    std::vector<Airplane> a;
    for (int i = 0; i < 100000;   i) {
        int arrival = arr_dist(eng);
        int departure = arrival   (20   lround(dep_dist(eng))) * 60;
        departure = min(departure, 24*60*60);
        a.push_back({ arrival, departure });
    }

    Schedule s(a);
    {
        const auto& start = steady_clock::now();
        int mnp = s.MaximumNumberOfPlanes();
        const auto& stop = steady_clock::now();
        duration<double> elapsed = stop - start;
        std::cout << "MaximumNumberOfPlanes : " << mnp << " - Elapsed: " << elapsed.count() << " s\n";
    }
    {
        const auto& start = steady_clock::now();
        int mnp = s.MaximumNumberOfPlanes2();
        const auto& stop = steady_clock::now();
        duration<double> elapsed = stop - start;
        std::cout << "MaximumNumberOfPlanes2: " << mnp << " - Elapsed: " << elapsed.count() << " s\n";
    }
    return 0;
}

This gives (on my laptop):

MaximumNumberOfPlanes : 2572 - Elapsed: 48.8979 s
MaximumNumberOfPlanes2: 2572 - Elapsed: 0.0010778 s