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

Notice

If landing and flying happens at the same time, we consider landing should happen at first.

Have you met this question in a real interview?

Yes

Example

For interval list

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

Return3

/**

* 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 cnt = 0, maxCnt = 0;

    vector<pair<int, int>> points;

    for \(auto interval : airplanes\) {

        points.push\_back\({interval.start, 1}\);

        points.push\_back\({interval.end, 0}\);

    }

    sort\(points.begin\(\), points.end\(\)\);

    for \(auto point : points\) {

        if \(point.second > 0\) {

            ++cnt;

        } else {

            --cnt;

        }

        maxCnt = max\(cnt, maxCnt\);

    }

    return maxCnt;

}

};