📑 题目：56. 合并区间

🚀 本题 LeetCode 传送门

题目大意

合并给的多个区间，区间有重叠的要进行区间合并。

解题思路

先按照区间起点进行排序。然后从区间起点小的开始扫描，依次合并每个有重叠的区间。

代码

  1. package leetcode
  3. /**
  4.  * Definition for an interval.
  5.  * type Interval struct {
  6.  *    Start int
  7.  *    End   int
  8.  * }
  9.  */
  11. // Interval define
  12. type Interval struct {
  13.  Start int
  14.  End   int
  15. }
  17. func merge56(intervals []Interval) []Interval {
  18.  if len(intervals) == 0 {
  19.   return intervals
  20.  }
  21.  quickSort(intervals, 0, len(intervals)-1)
  22.  res := make([]Interval, 0)
  23.  res = append(res, intervals[0])
  24.  curIndex := 0
  25.  for i := 1; i < len(intervals); i++ {
  26.   if intervals[i].Start > res[curIndex].End {
  27.    curIndex++
  28.    res = append(res, intervals[i])
  29.   } else {
  30.    res[curIndex].End = max(intervals[i].End, res[curIndex].End)
  31.   }
  32.  }
  33.  return res
  34. }
  36. func max(a int, b int) int {
  37.  if a > b {
  38.   return a
  39.  }
  40.  return b
  41. }
  43. func min(a int, b int) int {
  44.  if a > b {
  45.   return b
  46.  }
  47.  return a
  48. }
  50. func partitionSort(a []Interval, lo, hi int) int {
  51.  pivot := a[hi]
  52.  i := lo - 1
  53.  for j := lo; j < hi; j++ {
  54.   if (a[j].Start < pivot.Start) || (a[j].Start == pivot.Start && a[j].End < pivot.End) {
  55.    i++
  56.    a[j], a[i] = a[i], a[j]
  57.   }
  58.  }
  59.  a[i+1], a[hi] = a[hi], a[i+1]
  60.  return i + 1
  61. }
  62. func quickSort(a []Interval, lo, hi int) {
  63.  if lo >= hi {
  64.   return
  65.  }
  66.  p := partitionSort(a, lo, hi)
  67.  quickSort(a, lo, p-1)
  68.  quickSort(a, p+1, hi)
  69. }