Try   HackMD

【LeetCode】 56. Merge Intervals

Description

Given a collection of intervals, merge all overlapping intervals.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

給予一個區間的集合,合併所有重疊到的區間。
注意: 2019年4月15日更改輸入型別,請重置成預設的程式碼並使用新的方法撰寫。

Example:

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].


Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

  • 先讓區間集合按大小排序。
  • s是第一個區間的開頭、e是第一個區間的結尾:
    • 如果接下來的區間落在se之間,就將e擴大。
    • 如果沒有落在這區間,就執行合併。

Code

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> ans; sort(intervals.begin(), intervals.end()); bool first = false; int s, e; for(int i = 0; i < intervals.size(); i++) { if(!first) { first = true; s = intervals[i][0]; e = intervals[i][1]; if(i == intervals.size() - 1) ans.push_back(vector<int>{s, e}); } else if(intervals[i][0] <= e) { e = max(e, intervals[i][1]); if(i == intervals.size() - 1) ans.push_back(vector<int>{s, e}); } else { ans.push_back(vector<int>{s, e}); first = false; i--; } } return ans; } };
tags: LeetCode C++