Array - 56. Merge Intervals
- Merge Intervals
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]
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
思路:
题目意思是合并区间,做法是可以先排序,再遍历区间集合,根据区间首尾来判断是否合并。
代码:
golang:
type myInterval [][]int
func (intervals myInterval)Len() int { return len(intervals) }
func (intervals myInterval)Less(i, j int) bool { return intervals[i][0] < intervals[j][0] }
func (intervals myInterval)Swap(i, j int) {
intervals[i], intervals[j] = intervals[j], intervals[i]
}
func (intervals myInterval)back() []int {
return intervals[len(intervals) - 1]
}
func (intervals *myInterval)pushBack(interval []int) {
*intervals = append(*intervals, interval)
}
func (intervals *myInterval)modifyBack(i, j int) {
if i > j {
(*intervals)[len(*intervals) - 1][1] = i
} else {
(*intervals)[len(*intervals) - 1][1] = j
}
}
func merge(intervals myInterval) [][]int {
sort.Sort(&intervals)
var res myInterval
for _, interval := range intervals {
if len(res) == 0 || interval[0] > res.back()[1] {
res.pushBack(interval)
} else {
// merge
res.modifyBack(interval[1], res.back()[1])
}
}
return res
}
// use sort
import "sort"
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 || len(intervals[0]) == 0 {
return nil
}
// sort
sort.Slice(intervals, func(i, j int) bool{
return intervals[i][0] < intervals[j][0]
})
for k := range intervals {
sort.Slice(intervals[k], func(i, j int) bool {
return intervals[k][i] < intervals[k][j]
})
}
var res [][]int
for i := range intervals {
if len(res) == 0 || res[len(res) - 1][1] < intervals[i][0] {
res = append(res, intervals[i])
} else {
res[len(res) - 1][1] = max(res[len(res) - 1][1], intervals[i][1])
}
}
return res
}
func max(i, j int) int {
if i < j {
return j
}
return i
}
Java:
class Solution {
/*public int[][] merge(int[][] intervals) {
List<int[]> merged = new ArrayList<>();
if (intervals.length == 0 || intervals == null) return merged.toArray(new int[0][]);
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int i = 0;
while (i < intervals.length) {
int left = intervals[i][0];
int right = intervals[i][1];
while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
i++;
right = Math.max(right, intervals[i][1]);
}
merged.add(new int[]{left, right});
i++;
}
return merged.toArray(new int[0][]);
}*/
public int[][] merge(int[][] intervals) {
int length=intervals.length;
if(length<=1)
return intervals;
int[] start = new int[length];
int[] end = new int[length];
for(int i=0;i<length;i++){
start[i]=intervals[i][0];
end[i]=intervals[i][1];
}
Arrays.sort(start);
Arrays.sort(end);
int startIndex=0;
int endIndex=0;
List<int[]> result = new LinkedList<>();
while(endIndex<length){
//as endIndex==length-1 is evaluated first, start[endIndex+1] will never hit out of index
if(endIndex==length-1 || start[endIndex+1]>end[endIndex]){
result.add(new int[]{start[startIndex],end[endIndex]});
startIndex=endIndex+1;
}
endIndex++;
}
return result.toArray(new int[result.size()][]);
}
}