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?

Example

For interval list

[
  [1,10],
  [2,3],
  [5,8],
  [4,7]
]

Return3
S: sweep line

将区间拆分成 起、落节点并排序，每次碰到起节点count++落节点count--

/**
 * 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.
     */
    struct TimeNode {
        int time;
        bool flying;
        TimeNode(int t, bool f): time(t), flying(f) {}
    };

    int countOfAirplanes(vector<Interval> &airplanes) {
        int size = airplanes.size();
        int count = 0;
        int maxCount = 0;
        vector<TimeNode*> times(size);
        for (int i = 0; i < size; ++i) {
            TimeNode node1(airplanes[i].start, true);
            TimeNode node2(airplanes[i].end, false);
            times[i * 2] = &node1;
            times[i * 2 + 1] = &node2;
        }
        sort(times.begin(), times.end(), cmp);
        for (TimeNode* i : times) {
            if (i->flying) {                                             
                count++;
            } else {
                count--;
            }
            maxCount = max(count, maxCount);
        }
        return maxCount;
    }

    bool cmp(TimeNode* a, TimeNode* b) {
        if (a->time == b->time) {
            if (a->flying && !b->flying) {
                return false;
            } else {
                return true;
            }
        }
        return a->time < b->time;
    }


};