Pythonでのマージ間隔

間隔のコレクションがあるとすると、重複するすべての間隔をマージする必要があります。したがって、間隔が[[1,3]、[2,6]、[8,10]、[15,18]]の場合、マージ後の間隔は[[1,6]、[8,10]になります。 ]、[15,18]]。これは、重複する2つの間隔があり、間隔が[1,3]と[2,6]であり、これらが[1,6]

手順を見てみましょう-

• 間隔リストの長さが0の場合、空白のリストを返します
• クイックソートメカニズムを使用して間隔リストを並べ替える
• stack：=空のスタックで、intervals[0]をスタックに挿入します
• 範囲1から間隔の長さのiの場合– 1
  • last_element：=スタックの最上位要素
  • last_elementの終わり>=間隔[i]の最初の要素の場合、
    • last_elementの終わり=間隔の終わりの最大値[i]、およびlast_elementの終わり
    • スタックから要素をポップ
    • last_elementをスタックにプッシュします
  • それ以外の場合は間隔[i]をスタックにプッシュします
• スタックを返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def merge(self, intervals):
      """
      :type intervals: List[Interval]
      :rtype: List[Interval]
      """
      if len(intervals) == 0:
         return []
      self.quicksort(intervals,0,len(intervals)-1)
      #for i in intervals:
         #print(i.start, i.end)
      stack = []
      stack.append(intervals[0])
      for i in range(1,len(intervals)):
         last_element= stack[len(stack)-1]
         if last_element[1] >= intervals[i][0]:
            last_element[1] = max(intervals[i][1],last_element[1])
            stack.pop(len(stack)-1)
            stack.append(last_element)
         else:
            stack.append(intervals[i])
      return stack
   def partition(self,array,start,end):
      pivot_index = start
      for i in range(start,end):
         if array[i][0]<=array[end][0]:
            array[i],array[pivot_index] =array[pivot_index],array[i]
            pivot_index+=1
      array[end],array[pivot_index] =array[pivot_index],array[end]
      return pivot_index
   def quicksort(self,array,start,end):
      if start<end:
         partition_index = self.partition(array,start,end)
         self.quicksort(array,start,partition_index-1)
         self.quicksort(array, partition_index + 1, end)
ob1 = Solution()
print(ob1.merge([[1,3],[2,6],[8,10],[15,18]]))

入力

[[1,3],[2,6],[8,10],[15,18]]

出力

[[1, 6], [8, 10], [15, 18]]