אתגר תכנותי: מחיקת מרווחים שאינם חופפים

האתגר מבוסס על leetcode 435 : Non-overlapping intervals

האתגר: בהינתן מערך של מרווחים כאשר intervals[i] = [start_i, end_i], יש להחזיר את מספר המרווחים הקטן ביותר אותם צריך להסיר כדי ששאר המרווחים לא יהיו חופפים.

שים לב שמרווחים שנוגעים זה בזה רק בנקודה מסוימת אינם חופפים. לדוגמה, [1, 2] ו- [2, 3] אינם חופפים.

דוגמה 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1

הסבר: מספיק להסיר את המרווח [1,3] וכל יתר המרווחים אינם חופפים.

דוגמה 2:

Input: intervals = [[2,3],[2,3],[2,3]]
Output: 2

הסבר: הסרת שני מרווחים [2,3] מסירה את כל החפיפות.

דוגמה 3:

Input: intervals = [[2,4],[4,5]]
Output: 0

הסבר: אין חפיפה ולכן אין צורך להסיר.

פתרון מוצע

def erase_overlapping_intervals(intervals):
   if not intervals:
       return 0
   
   len_intervals = len(intervals)
   
   # 1. Sort by the END time (x[1])
   intervals.sort(key=lambda x: x[1])
  
   # 2. Keep the first interval since it ends earliest
   count_kept = 1
   last_kept_end = intervals[0][1]
  
   # 3. Iterate from the second interval onwards
   for i in range(1, len_intervals):
       # If the current interval starts after (or exactly at) the place where the last one ended...
       if last_kept_end <= intervals[i][0]: # No overlap
           # So keep it.
           count_kept += 1
           last_kept_end = intervals[i][1] # Update the end time
       # else: (it overlaps)
           # Erase by not keeping
           # e.g. not updating count_kept or last_kept_end.
          
   # 4. Calculate the number removed
   return len_intervals - count_kept

קוד לבדיקה:

test_cases = [
   [
       [[1,2],[2,3],[3,4],[1,3]], 1 # [1,3]
   ],
   [
       [[1,2],[1,2],[1,2]], 2 # remove two intervals
   ],
   [
       [[1,2],[2,3]], 0
   ],
   [
       [[1,10],[2,5],[6,8]], 1
   ]
]

print(f"{'Result'.ljust(6)}{' '*4}{'Expected'.ljust(10)}")
print(f"{'-'*6}{'-'*4}{'-'*10}{'-'*4}")
for intervals, exp_res in test_cases:
   actual_res = erase_overlapping_intervals(intervals)
   conclusion = "😄" if actual_res == exp_res else "😭"
   sign = "==" if actual_res == exp_res else "!="
   print(f"{str(actual_res).ljust(6)}{sign.ljust(4)}{str(exp_res).ljust(10)}{conclusion}")

print("Finito Programa")

הסבר הפתרון

הפתרון משתמש באלגוריתם חמדן (Greedy) שאחד הרמזים לשימוש בו הוא הצורך לפתור בעיית אופטימיזציה.

רמז נוסף לפתרון הוא שבמקום לשאול: "מהו המספר המינימלי של מרווחים שצריך להסיר?" הפתרון שואל: "מהו המספר המקסימלי של מרווחים שאפשר לשמור מבלי שיחפפו?"

לאחר שמוצאים כמה מרווחים נשמרו max_kept, אפשר בקלות לחשב את התשובה באמצעות החסרה מסך כל המרווחים: total_intervals - max_kept

איך מוצאים את max_kept?

1. ממיינים את כל המרווחים לפי זמן הסיום שלהם (end).

2. שומרים את המרווח הראשון (זה שמסיים הכי מוקדם).

3. מגדירים משתנה last_kept_end לזמן הסיום שלו.

4. עוברים בלולאה על יתר המרווחים:

   • אם current_start >= last_kept_end אז אין חפיפה ולכן מוסיפים אחד למספר השמורים (count_kept += 1) ומעדכנים את last_kept_end.

   • אחרת יש חפיפה, ואז מספיק שלא מעדכנים את המשתנים העוקבים אחר המרווחים שהוסרו.

יישום האלגוריתם החמדן מצליח לפתור את הבעיה משום שהוא תמיד שומר את המרווח שמסתיים הכי מוקדם, ובכך משאיר את מירב המקום למרווחים עתידיים, מה שמביא לפתרון אופטימלי.

יעילות הפתרון

סיבוכיות זמן (Time Complexity):

• שלב המיון דורש O(n log n)
• המעבר על הרשימה לאחר מכן אורך O(n)

סה"כ: O(n log⁡ n)

סיבוכיות מקום (Space Complexity):

נדרשת רק כמות זניחה של זיכרון נוסף (למשתנים בודדים). לכן: O(1).

אולם אם מביאים בחשבון את פונקצית המיון המובנה של פייתון אשר משתמשת באלגוריתם Timsort אז לכל היותר O(n).

סיכום

הבעיה של מחיקת מרווחים חופפים מדגימה כיצד אלגוריתם חמדן יכול לפתור בעיות אופטימיזציה ביעילות כאשר במקום לבדוק את כל האפשרויות (מה שהיה דורש זמן מעריכי), מסתפקים בבחירה מקומית מיטבית אשר שומרת תמיד את המרווח שמסתיים מוקדם ביותר. הודות לכך, הפתרון פשוט, קצר, אלגנטי, ויעיל מאוד.

העיקרון שניתן ללמוד מהבעיה הזו הוא שכאשר מנסים למקסם מספר בחירות שאינן חופפות בזמן (כמו פגישות, משימות, או מרווחים), מיון לפי זמן סיום עשוי להיות מועיל במיוחד.

מדריכים נוספים שעשויים לעניין אותך

אתגר תכנותי: מיזוגי מרווחים

אתגר תכנותי: הכנסת מרווח Insert Interval

אתגר תכנותי: מספר הרכיבים המחוברים בגרף לא מכוון

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים