アルゴリズム 体操23 Merge Intervals

Merge Intervals

インターバルリストを引数として、重複するすべてのインターバルをマージして、相互に排他的なインターバルのみを持つリストを作成します。

例

Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
理由: 最初の2つの区間[1,4]と[2,5]は重複しているので、それらを[1,5]

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]

Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]

Solution

a.start <= b.startである、2つのインターバル（"a" と "b"）の例を見てみましょう。次の4つのシナリオが考えられます。

1. a と　b　が重ならない。
2. b　の一部が a　に重なる
3. b が a　に完全に重なる
4. a が b　と完全に重なり、二つのスタートポイントが同じ。

例えば、こんな感じです。

1. 開始時刻の間隔を並べ替えて、a.start <= b.start
2. a が b と重なっている場合 （つまり、b.start <= a.end）は、次のような新しいインターバル c にマージする必要があります。
3. 上記の2つのステップを繰り返して、c が 次のインターバルと重複する場合は c を次のインターバルにマージします。

実装

class Interval:
  def __init__(self, start, end):
    self.start = start
    self.end = end

  def print_interval(self):
    print("[" + str(self.start) + ", " + str(self.end) + "]", end='')

def merge(intervals):
  if len(intervals) < 2:
    return intervals

  # sort the intervals on the start time
  intervals.sort(key=lambda x: x.start)

  mergedIntervals = []
  start = intervals[0].start
  end = intervals[0].end
  for i in range(1, len(intervals)):
    interval = intervals[i]
    if interval.start <= end:  # overlapping intervals, adjust the 'end'
      end = max(interval.end, end)
    else:  # non-overlapping interval, add the previous internval and reset
      mergedIntervals.append(Interval(start, end))
      start = interval.start
      end = interval.end

  # add the last interval
  mergedIntervals.append(Interval(start, end))
  return mergedIntervals


def main():
  print("Merged intervals: ", end='')
  for i in merge([Interval(1, 4), Interval(2, 5), Interval(7, 9)]):
    i.print_interval()
  print()

  print("Merged intervals: ", end='')
  for i in merge([Interval(6, 7), Interval(2, 4), Interval(5, 9)]):
    i.print_interval()
  print()

  print("Merged intervals: ", end='')
  for i in merge([Interval(1, 4), Interval(2, 6), Interval(3, 5)]):
    i.print_interval()
  print()


main()