合并區(qū)間

題目

給出一個區(qū)間的集合概龄，請合并所有重疊的區(qū)間。

• 示例1：

  輸入: [[1,3],[2,6],[8,10],[15,18]]
  輸出: [[1,6],[8,10],[15,18]]
  解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
  

• 示例2：

  輸入: [[1,4],[4,5]]
  輸出: [[1,5]]
  解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間熬词。
  

解答

• 思路：

  • 首先對輸入的區(qū)間數(shù)組進行排序旁钧；
  • 接著用兩個指針，cur指向當前處理的區(qū)間互拾，next指向下一個要處理的區(qū)間歪今；
  • 根據(jù)cur和next所指區(qū)間的情況，分別處理：
    • intervals[cur] 和 intervals[next]區(qū)間沒有重疊颜矿，則令intervals[cur + 1] = intervals[next], cur++, next++
    • intervals[cur][1]= intervals[next][0]寄猩，則令 intervals[cur][1] = max(intervals[cur][1], intervals[next][1]), next++

• 代碼：

  def merge(self, intervals):
      """
      :type intervals: List[List[int]]
      :rtype List[List[int]]
  
      (Knowledge)
  
      思路：
      1. 首先對輸入的區(qū)間數(shù)組進行排序；
      2. 接著用兩個指針骑疆，cur指向當前處理的區(qū)間田篇，next指向下一個要處理的區(qū)間替废；
      3. 根據(jù)cur和next所指區(qū)間的情況，分別處理：
          - intervals[cur] 和 intervals[next]區(qū)間沒有重疊泊柬，則令intervals[cur + 1] = intervals[next], cur++, next++
          - intervals[cur][1] >= intervals[next][0]椎镣，則令intervals[cur][1] = max(intervals[cur][1], intervals[next][1]), next++
      4. 最后返回intervals[:cur + 1]
      """
  
      # 首先對輸入的區(qū)間數(shù)組進行排序
      intervals = sorted(intervals)
      cur, next = 0, 1
  
      while next < len(intervals):
          if intervals[next][0] > intervals[cur][1]:  # 處理沒有重疊的情況
              intervals[cur + 1], cur, next = intervals[next], cur + 1, next + 1
          else:   # 處理有重疊的情況
              intervals[cur][1], next = max(intervals[cur][1], intervals[next][1]), next + 1
  
      return intervals[:cur + 1]
  

測試驗證

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype List[List[int]]

        (Knowledge)

        思路：
        1. 首先對輸入的區(qū)間數(shù)組進行排序；
        2. 接著用兩個指針兽赁，cur指向當前處理的區(qū)間状答，next指向下一個要處理的區(qū)間；
        3. 根據(jù)cur和next所指區(qū)間的情況刀崖，分別處理：
            - intervals[cur] 和 intervals[next]區(qū)間沒有重疊惊科，則令intervals[cur + 1] = intervals[next], cur++, next++
            - intervals[cur][1] >= intervals[next][0]，則令intervals[cur][1] = max(intervals[cur][1], intervals[next][1]), next++
        4. 最后返回intervals[:cur + 1]
        """

        # 首先對輸入的區(qū)間數(shù)組進行排序
        intervals = sorted(intervals)
        cur, next = 0, 1

        while next < len(intervals):
            if intervals[next][0] > intervals[cur][1]:  # 處理沒有重疊的情況
                intervals[cur + 1], cur, next = intervals[next], cur + 1, next + 1
            else:  # 處理有重疊的情況
                intervals[cur][1], next = max(intervals[cur][1], intervals[next][1]), next + 1

        return intervals[:cur + 1]


if __name__ == '__main__':
    solution = Solution()
    print(solution.merge([[1, 3], [2, 6], [8, 10], [15, 18]]), "= [[1, 6], [8, 10], [15, 18]]")
    print(solution.merge([[1, 4], [4, 5]]), "= [[1, 5]]")