0056. Merge Intervals

# 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)
}

``````

Apr 8, 2023