56. 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].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
题目大意 #
合并给的多个区间，区间有重叠的要进行区间合并。
解题思路 #
先按照区间起点进行排序。然后从区间起点小的开始扫描，依次合并每个有重叠的区间。
代码 #
package leetcode
/**
* Definition for an interval.
* type Interval struct {
* Start int
* End int
* }
*/
// Interval define
type Interval struct {
Start int
End int
}
func merge56(intervals []Interval) []Interval {
if len(intervals) == 0 {
return intervals
}
quickSort(intervals, 0, len(intervals)-1)
res := make([]Interval, 0)
res = append(res, intervals[0])
curIndex := 0
for i := 1; i < len(intervals); i++ {
if intervals[i].Start > res[curIndex].End {
curIndex++
res = append(res, intervals[i])
} else {
res[curIndex].End = max(intervals[i].End, res[curIndex].End)
}
}
return res
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func min(a int, b int) int {
if a > b {
return b
}
return a
}
func partitionSort(a []Interval, lo, hi int) int {
pivot := a[hi]
i := lo - 1
for j := lo; j < hi; j++ {
if (a[j].Start < pivot.Start) || (a[j].Start == pivot.Start && a[j].End < pivot.End) {
i++
a[j], a[i] = a[i], a[j]
}
}
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
}
func quickSort(a []Interval, lo, hi int) {
if lo >= hi {
return
}
p := partitionSort(a, lo, hi)
quickSort(a, lo, p-1)
quickSort(a, p+1, hi)
}