56 Merge Intervals 合并區(qū)間
Description:
Given a collection of intervals, merge all overlapping intervals.
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.
NOTE:
input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
題目描述:
給出一個(gè)區(qū)間的集合，請(qǐng)合并所有重疊的區(qū)間再扭。
示例 :
示例 1:
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間财边。
思路:
- 排序, 將 intervals數(shù)組中的第一個(gè)元素排序
- 遍歷intervals數(shù)組
- 如果結(jié)果數(shù)組為空數(shù)組或者結(jié)果數(shù)組中的最后一個(gè)元素的右側(cè)比 intervals當(dāng)前元素的左側(cè)還要小, 加入結(jié)果數(shù)組
- 否則比較結(jié)果數(shù)組中的最后一個(gè)元素的右側(cè)和 intervals當(dāng)前元素的右側(cè), 取較大的元素
時(shí)間復(fù)雜度O(nlgn), 空間復(fù)雜度O(lgn)
代碼:
C++:
class Solution
{
public:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
for (auto &i : intervals)
{
if (result.empty() or i[0] > result.back()[1]) result.push_back(i);
else result.back()[1] = max(result.back()[1], i[1]);
}
return result;
}
};
Java:
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int result[][] = new int[intervals.length][2], i = -1;
for (int[] interval: intervals) {
if (i == -1 || interval[0] > result[i][1]) result[++i] = interval;
else result[i][1] = Math.max(result[i][1], interval[1]);
}
return Arrays.copyOf(result, i + 1);
}
}
Python:
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
result = []
intervals.sort()
for i in intervals:
if not result or result[-1][1] < i[0]:
result.append(i)
else:
result[-1][1] = max(result[-1][1], i[1])
return result
