首页 > 代码库 > [LeetCode] Merge Intervals

[LeetCode] Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

 1 /** 2  * Definition for an interval. 3  * struct Interval { 4  *     int start; 5  *     int end; 6  *     Interval() : start(0), end(0) {} 7  *     Interval(int s, int e) : start(s), end(e) {} 8  * }; 9  */10  11 bool cmp(const Interval &a, const Interval &b) {12     return a.start < b.start;13 }14     15 class Solution {16 public:17     vector<Interval> merge(vector<Interval> &intervals) {18         int pos = 0, cnt = 0;19         sort(intervals.begin(), intervals.end(), cmp);20         for (int i = 1; i < intervals.size(); ++i) {21             if (intervals[pos].end >= intervals[i].start) {22                     ++cnt;23                     if (intervals[pos].end <= intervals[i].end) {24                         intervals[pos].end = intervals[i].end;25                     }26             } else {27                 ++pos;28                 intervals[pos].start = intervals[i].start;29                 intervals[pos].end = intervals[i].end;30             }31         }32         intervals.resize(intervals.size()-cnt);33         return intervals;34     }35 };

 

[LeetCode] Merge Intervals