LintCode: Number of Airplanes in the Sky

 1 /**
 2  * Definition of Interval:
 3  * classs Interval {
 4  *     int start, end;
 5  *     Interval(int start, int end) {
 6  *         this->start = start;
 7  *         this->end = end;
 8  *     }
 9  */
10 class Solution {
11 public:
12     /**
13      * @param intervals: An interval array
14      * @return: Count of airplanes are in the sky.
15      */
16     int countOfAirplanes(vector<Interval> &airplanes) {
17         // write your code here
18         vector<pair<int, int> > v;
19         for (auto &i : airplanes) {
20             v.push_back(make_pair(i.start, 1));
21             v.push_back(make_pair(i.end, -1));
22         }
23         int cnt = 0, res = 0;
24         sort(v.begin(), v.end());
25         for (auto &i : v) {
26             cnt += i.second;
27             res = max(cnt, res);
28         }
29         return res;
30     }
31 };

 1 /**
 2  * Definition of Interval:
 3  * classs Interval {
 4  *     int start, end;
 5  *     Interval(int start, int end) {
 6  *         this->start = start;
 7  *         this->end = end;
 8  *     }
 9  */
10 class Solution {
11 public:
12     /**
13      * @param intervals: An interval array
14      * @return: Count of airplanes are in the sky.
15      */
16     int countOfAirplanes(vector<Interval> &airplanes) {
17         // write your code here
18         int fly[30] = {0};
19         int land[30] = {0};
20         int len = airplanes.size();
21         for (int i = 0; i < len; i++ ) {
22             fly[airplanes[i].start] ++;
23             land[airplanes[i].end] --;
24         }
25         int max = 0, cur = 0;
26         for (int i = 0; i < 30; i++ ) {
27             cur = cur + fly[i] + land[i];
28             if (cur > max) {
29                 max = cur;
30             }
31         }
32         return max;
33     }
34 };