- 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：
代码语言：javascript复制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
}Java：
代码语言：javascript复制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()][]);
}
}
