[PYTHON] Algorithmus Gymnastik 23 Zusammenführungsintervalle

Merge Intervals Nimmt eine Intervallliste als Argument und führt alle doppelten Intervalle zusammen, um eine Liste mit nur sich gegenseitig ausschließenden Intervallen zu erstellen.

Beispiel

Intervals: [[1,4], [2,5], [7,9]] Output: [[1,5], [7,9]] Grund: Die ersten beiden Intervalle [1,4] und [2,5] überlappen sich, also machen Sie sie [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 Schauen wir uns ein Beispiel für zwei Intervalle ("a" und "b") an, in denen a.start <= b.start. Es gibt vier mögliche Szenarien:

1. a und b überlappen sich nicht.
2. Ein Teil von b überlappt mit a
3. b überlappt a vollständig
4. a überlappt sich vollständig mit b und die beiden Startpunkte sind gleich.

Zum Beispiel sieht es so aus.

1. Sortieren Sie die Startzeitintervalle und a.start <= b.start
2. Wenn a b überlappt (dh b.start <= a.end), müssen Sie es in einem neuen Intervall c wie folgt zusammenführen:
3. Wiederholen Sie die beiden obigen Schritte, um c in das nächste Intervall einzufügen, wenn sich c mit dem nächsten Intervall überschneidet.

Implementierung

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()