Gymnastique algorithmique 23 Intervalles de fusion

Merge Intervals Prend une liste d'intervalles comme argument et fusionne tous les intervalles en double pour créer une liste avec uniquement des intervalles mutuellement exclusifs.

Exemple

Intervals: [[1,4], [2,5], [7,9]] Output: [[1,5], [7,9]] Raison: Les deux premiers intervalles [1,4] et [2,5] se chevauchent, alors faites-les [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 Regardons un exemple de deux intervalles ("a" et "b") où a.start <= b.start. Il existe quatre scénarios possibles:

1. a et b ne se chevauchent pas.
2. Une partie de b chevauche un
3. b chevauche complètement a
4. a chevauche complètement b et les deux points de départ sont identiques.

Par exemple, cela ressemble à ceci.

1. Triez les intervalles de temps de début et a.start <= b.start
2. Si a chevauche b (c'est-à-dire b.start <= a.end), vous devez le fusionner dans un nouvel intervalle c comme ceci:
3. Répétez les deux étapes ci-dessus pour fusionner c dans l'intervalle suivant si c chevauche l'intervalle suivant.

la mise en oeuvre

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