LintCode – Number of Airplanes in the Sky

LintCode – Number of Airplanes in the Sky

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

c++: using priority_queue

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
public:
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        // write your code here
        int size = airplanes.size();
        if (size <= 0) return 0;
        priority_queue<Interval, vector<int>, greater<int>> pq;
        sort(airplanes.begin(), airplanes.end(), 
                    [](Interval a, Interval b) {return a.start < b.start;});
        int i, airplaneCount = 0;
        for (i=0; i<size; i++) {
            if (pq.empty()) {
                pq.push(airplanes[i].end);
                airplaneCount ++;
                continue;
            }
            if (airplanes[i].start >= pq.top()) {
                pq.pop();
                pq.push(airplanes[i].end);
            } else {
                pq.push(airplanes[i].end);
                airplaneCount ++;
            }
        }
        return airplaneCount;
    }
};

c++:

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
public:
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        // write your code here
        vector<int> s(airplanes.size());
        vector<int> e(airplanes.size());
        for(int i = 0; i < airplanes.size(); i++) {
            s[i] = airplanes[i].start;
            e[i] = airplanes[i].end;
        }
        sort(s.begin(), s.end());
        sort(e.begin(), e.end());
        int eIndex = 0, planes = 0, available = 0;
        for(int i=0; i<s.size(); i++) {
            while(e[eIndex] <= s[i]) {
                available++;
                eIndex++;
            }
            if(available > 0)
                available--;
            else
                planes++;
        }
        return planes;
    }
};

Leave a Reply

Your email address will not be published.