[LintCode] Number of Airplanes i

Problem

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.

Example
For interval list

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

Return 3

Solution

扫描线做法。先把每个点排序，0代表起飞，1代表降落。然后扫描这些点，根据起飞和降落来count++和count--。最后某一时间最大的count就是所求。

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
bool comp(const pair<int, int> &lhs, const pair<int, int> &rhs) {
    if (lhs.first < rhs.first) {
        return true;
    } else if (lhs.first == rhs.first) {
        return lhs.second >= rhs.second;
    } else {
        return false;
    }
}

class Solution {
    
public:
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        vector<pair<int, int>> info;
        for(int i = 0; i < airplanes.size(); i++) {
            pair<int, int> up(airplanes[i].start, 0);
            info.push_back(up);
            pair<int, int> down(airplanes[i].end, 1);
            info.push_back(down);
        }
        
        sort(info.begin(), info.end(), comp);
        int count = 0;
        int maxCount = 0;
        for(int i = 0; i < info.size(); i++) {
            if (info[i].second == 0) {
                count++;
            } else {
                count--;
            }
            maxCount = max(maxCount, count);
        }
        
        return maxCount;
    }
};