LeetCode --- 56. Merge Intervals

タイトルリンク: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]. 

この問題の要求は,与えられた間隔のセットに重なるものを統合することである.
間隔をマージするには、まず隣接する間隔を見つけてから、重複しているかどうかを見て、ある場合はマージします.
そこで,まず配列の並べ替えを考える.ソートする場合は、間隔の開始時間でソートするだけです.次に配列を巡回し、現在の間隔の終了時間は現在の間隔の開始時間より小さくなく、重複があることを示し、マージする必要があります.マージすると、新しい間隔の終了時間は、この2つの間隔の終了時間の最大値に等しくなります.
実装の過程で、まず最初の間隔を新しい配列に配置し、それから2番目から後で遍歴し、重複があれば、新しい配列の最後の要素の終了時間を変更します.オーバーラップがない場合は、新しい配列に追加します.
時間複雑度:O(nlogn)
空間複雑度:O(n)

 1 bool cmp(Interval i1, Interval i2)
 2 {
 3     return i1.start < i2.start;
 4 }
 5 
 6 class Solution
 7 {
 8 public:
 9     vector<Interval> merge(vector<Interval> &intervals)
10     {
11         vector<Interval> vi;
12 
13         if(intervals.size() == 0)
14             return vi;
15 
16         sort(intervals.begin(), intervals.end(), cmp);
17 
18         vi.push_back(intervals[0]);
19         for(int i = 1; i < intervals.size(); ++ i)
20         {
21             if(vi[vi.size() - 1].end >= intervals[i].start)
22                 vi[vi.size() - 1].end = max(vi[vi.size() - 1].end, intervals[i].end);
23             else
24                 vi.push_back(intervals[i]);
25         }
26         return vi;
27     }
28 };

転載は出典を説明してください:LeetCode---56.Merge Intervals