56. Merge Intervals
Leetcode
題目
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.解答
方法一
首先我們先來看一個新的元素，如果要加入到原本的矩陣中，會有幾種情況：
假設原本已有的元素為：[[1, 6], [8, 12], [15, 19]]
新加入的元素為
[5, 9]- 左端點及右端點分別在不同的節點
合併完的矩陣為：[[1, 12], [15, 19]]
=> 這種情況會將原有的 [1, 6], [8, 12] 刪除，並加入 [1, 12] 到矩陣裡
新加入的元素為
[5, 7]- 左端點有對應節點，右端點沒有
合併完的矩陣為：[[1, 7], [8, 12], [15, 19]]
=> 將原有的 [1, 6] 刪除，，並加入 [1, 7] 到矩陣裡
新加入的元素為
[7, 9]- 右端點有對應節點，左端點沒有
合併完的矩陣為：[[1, 6], [7, 12], [15, 19]]
=> 將原有的 [8, 12] 刪除，，並加入 [7, 12] 到矩陣裡
新加入的元素為
[9, 10]- 左端點及右端點都在同一個節點
合併完的矩陣為：[[1, 6], [8, 12], [15, 19]]
=> 原有矩陣不需要處理
新加入的元素為
[20, 23]- 左端點及右端點都不在原有的節點裡
合併完的矩陣為：[[1, 6], [8, 12], [15, 19], [20, 23]]
=> 將新加入的元素直接加進原有矩陣
新加入的元素為
[1, 100]- 左端點及右端點把原有的節點覆蓋了
合併完的矩陣為：[[1, 100]]
=> 根據新加入元素的左右端點，判斷原有矩陣中哪些被覆蓋的元素需要被刪除
列出這六種可能的情況後接著就可以把這些狀況轉換為程式碼了
var merge = function (intervals) {
const ans = [intervals[0]];
// 將節點從 ans 中移除
const remove = (node) => {
const targetIndex = ans.findIndex(item => {
return item[0] === node[0] && item[1] === node[1]
});
if (targetIndex > -1) {
ans.splice(targetIndex, 1);
}
}
const isValidNodes = (start, end) => {
return start && end;
}
const isSameNode = (start, end) => {
if (!start && !end) return true
if (start && !end) return false
if (!start && end) return false
return start[0] === end[0] && start[1] === end[1];
}
// 從第二個節點開始遍歷每個節點
for (let i = 1; i < intervals.length; i++) {
const value = intervals[i];
let start = null;
let end = null;
for (let j = 0; j < ans.length; j++) {
// 找到左端點在哪個節點
if (value[0] >= ans[j][0] && value[0] <= ans[j][1]) {
start = ans[j]
}
// 找到右端點在哪個節點
if (value[1] >= ans[j][0] && value[1] <= ans[j][1]) {
end = ans[j]
}
// 判斷哪些節點被覆蓋了
if (value[0] < ans[j][0] && value[1] > ans[j][1]) {
// 情況 6. 左端點及右端點把原有的節點覆蓋了
// 刪除掉這些被覆蓋的元素
ans.splice(j, 1);
j--;
}
}
if (isValidNodes(start, end) && !isSameNode(start, end)) {
// 情況 1. 左端點及右端點分別在不同的節點
remove(start);
remove(end);
ans.push([start[0], end[1]]);
} else if (start && !end) {
// 情況 2. 左端點有對應節點，右端點沒有
remove(start);
ans.push([start[0], value[1]]);
} else if (!start && end) {
// 情況 3. 右端點有對應節點，左端點沒有
remove(end);
ans.push([value[0], end[1]]);
} else if (isValidNodes(start, end) && isSameNode(start, end)) {
// 情況 4. 左端點及右端點都在同一個節點
} else if (!start && !end) {
// 情況 5. 左端點及右端點都不在原有的節點裡
// 情況 6. 左端點及右端點把原有的節點覆蓋了
ans.push(value);
}
}
return ans;
};Runtime: 416 ms Beats 5.01% of users with JavaScript
Memory: 59.19 MB Beats 48.59% of users with JavaScript
時間複雜度: O(n^2)
要先遍歷一次 原有的矩陣 (intervals)，然後又要遍歷 merge 過後的矩陣 (ans)
空間複雜度: O(n)
ans 拿來儲存答案
方法二
可以看到方法一需要列出所有可能的六種情況，接著判斷新加入的元素與每個原有節點之間的關係，這樣寫出一堆 if else 非常的複雜而且也容易出錯
在方法一的過程中，我們需要判斷新加入的元素其左、右端點分別在哪個既有節點上，所以需要去遍歷 ans 矩陣，換個方式想，如果一開始就先將矩陣排序好，當把新加入的元素加進來時，只需要判斷其左、右端點跟原有矩陣的最後一個節點之間的關係就好了，如果是這樣的話總共會有以下三種情況：
假設原本已有的元素為：[[1, 6]]
新加入的元素為
[7, 12]- 新加入元素的左端點比原有元素的右端點大
合併完的矩陣為：[[1, 6], [7, 12]]
新加入的元素為
[6, 12]- 新加入元素的左端點跟原有元素的右端點一樣大
合併完的矩陣為：[[1, 12]]
新加入的元素為
[3, 7]- 新加入元素的右端點比原有元素的右端點大
合併完的矩陣為：[[1, 7]]
新加入的元素為
[2, 3]- 新加入的元素被囊括在原有的元素裡 (剩下的情況)
合併完的矩陣為：[[1, 6]]
var merge = function (intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const ans = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = ans[ans.length - 1];
const value = intervals[i];
if (value[0] > last[1]) {
// 情況 1. 新加入元素的左端點比原有元素的右端點大
ans.push(value);
} else if (value[0] === last[1]) {
// 情況 2. 新加入元素的左端點跟原有元素的右端點一樣大
last[1] = value[1];
} else if (value[1] > last[1]) {
// 情況 3. 新加入元素的右端點比原有元素的右端點大
last[1] = value[1];
}
// 情況 4. 剩下的狀況 - 不需處理
}
return ans;
};Runtime: 99 ms Beats 49.59% of users with JavaScript
Memory: 58.58 MB Beats 63.93% of users with JavaScript
時間複雜度: O(nlog(n)) - 排序算法
空間複雜度: O(n) - 存儲 ans 矩陣
參考資料
Last updated
Was this helpful?