Merge Intervals (M)
題目
Given a collection of intervals, merge all overlapping intervals.
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.
題意
將給定陣列中所有互相重疊的區間合并為一個大區間，
思路
將區間按照左端點值排序后進行處理，
代碼實作
Java
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[][]{};
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
List<int[]> list = new ArrayList<>();
int left = intervals[0][0], right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int[] interval = intervals[i];
if (left <= interval[1] && right >= interval[0]) {
left = Math.min(left, interval[0]);
right = Math.max(right, interval[1]);
} else {
list.add(new int[]{left, right});
left = interval[0];
right = interval[1];
}
}
list.add(new int[]{left, right});
return list.toArray(new int[list.size()][]);
}
}
JavaScript
var merge = function(intervals) {
let ans = [];
if (intervals.length == 0) {
return ans;
}
intervals.sort((a, b) => a[0] - b[0]);
let left = intervals[0][0], right = intervals[0][1];
for (let interval of intervals) {
if (left <= interval[1] && right >= interval[0]) {
left = Math.min(left, interval[0]);
right = Math.max(right, interval[1]);
} else {
ans.push([left, right]);
left = interval[0];
right = interval[1];
}
}
ans.push([left, right]);
return ans;
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27698.html
標籤：其他
下一篇：5.排序（下）