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]

Screen Shot 2020-08-07 at 20.12.28.png

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. Screen Shot 2020-08-07 at 20.20.36.png

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

Recommended Posts

Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée