website/content.en/ChapterFour/0001~0099/0056.Merge-Intervals.md
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.
Merge the given intervals; intervals that overlap should be merged.
First sort the intervals by their starting points. Then scan from the interval with the smallest starting point, and merge each overlapping interval in order.
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)
}