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

Merge Intervals LeetCode 57

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

לאחר שבמדריך קודם התמודדנו עם האתגר של הכנסת מרווח קיים לתוך רצף מרווחים מסודרים במדריך זה נעלה ברמת הקושי ונתמודד עם מיזוג מרווחים.

האתגר במדריך יחזק אצלך מיומנויות חשובות, ובכללם:

• פירוק בעיה הנראית גדולה למרכיביה: מיון, מיזוג.

• שימוש באלגוריתם לינארי לפתרון בעיה שנראית במבט ראשון בעלת מורכבות מעריכית.

• פיתוח חשיבה ויזואלית על ציר הזמן.

האתגר "מיזוגי מרווחים"

נתון מערך של מרווחים כאשר:

intervals[i] = [starti, endi]

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

לדוגמה:

Input: intervals = [[4,6],[2,7]]
Output: [[2,7]]

דוגמה 2:

Input: intervals = [[1,3],[4,7],[8,9],[2,6]]
Output: [[1,7],[8,9]]

דוגמה 3:

Input: intervals = [[1,2],[3,5],[5,8]]
Output: [[1,2],[3,8]]

• אפילו איבר אחד משותף בין שני מרווחים נחשב כחפיפה.

רמז לפתרון

אחד האתגרים בפתרון האתגר הוא להבין מתי המרווחים חופפים.

כמו בדרך כלל, כדאי לנסות לשרבט את הבעיה כדי להיטיב את ההבנה.

נראה לדוגמה שני מרווחים חופפים a ו-b:

a1------a2
      b1-------b2

או:

b1------b2
      a1-------a2

המרווחים חופפים אם המקסימום של (a1, b1) קטן מאשר המינימום של (a2, b2).

ואם זה לא המצב אז הם אינם חופפים, לדוגמה:

a1------a2
                      b1-------b2

ננסח הבנה זו ביתר בהירות כך:

max(a1,b1) ≤ min(a2,b2)

בשלב זה, אתה מוזמן להציץ בפתרון אבל עדיף אם קודם תנסה לפתור בעצמך.

פתרון

def merge_intervals(intervals):
    # Sanitize
    if not intervals:
        return []
    
    # Step 1: sort by start time
    intervals.sort(key=lambda x: x[0])
    
    # Step 2: accumulate result
    res = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = res[-1][1]
        if max(start, res[-1][0]) <= min(end, last_end):  # overlap or touching
            res[-1][1] = max(end, last_end)
        else:
            res.append([start, end])

    return res

נסביר:

1. מתחילים מבדיקה האם ישנם מרווחים (intervals).
2. בצעד הראשון ממיינים את המרווחים על פי האיבר הראשון. צעד זה חיוני כדי שניתן יהיה למזג או להוסיף את המרווחים על פי סדר בצעד הבא.
3. בצעד השני עוברים אחד אחד מהמרווח השני ברצף, אם ישנה חפיפה אז ממזגים אחרת מוסיפים לרשימה המתארכת של תוצאות.
4. לבסוף, מחזירים את התוצאה.

הקוד הבא ישמש לבדיקת הפתרון:

# Test cases
test_cases = [
   [
       [[1,3],[2,6],[8,10],[15,18]],
       [[1,6],[8,10],[15,18]]
   ],
   [
       [[1,2],[4,9],[8,10],[13,14]],
       [[1,2],[4,10],[13,14]]
   ],
   [
       [[2,5],[8,10],[9,11]],
       [[2,5],[8,11]]
   ],
   [
       [[2,9],[7,11],[10,12]],
       [[2,12]]
   ],
   [
       [[1,4],[4,5]],
       [[1,5]]
   ],
   [
       [[4,7],[1,4]],
       [[1,7]]
   ],
]


print(f"{'Result'.ljust(30)}{' '*4}{'Expected'.ljust(30)}{' '.ljust(4)}")
print(f"{'-'*30}{'-'*4}{'-'*30}{'-'*4}")


for intervals, exp_res in test_cases:
   actual_res = merge_intervals(intervals)
   conclusion = "😄" if actual_res == exp_res else "😭"
   sign = "==" if actual_res == exp_res else "!="
   print(f"{str(actual_res).ljust(30)}{sign.ljust(4)}{str(exp_res).ljust(30)}{conclusion}")


print("Finito Programa")

הערכת יעילות

יעילות הזמן: אומנם יעילות המיזוג היא לינארית O(N) אבל משך המיון הוא O(N log N), ולכן סה"כ יעילות הזמן היא לינאריתמית.

יעילות מקום: את הרשימה הממוזגת מאחסנים ברשימת התוצאות res. צעד הדורש O(N) מקום נוסף בזכרון.

סיכום

באתגר "מיזוגי מרווחים" פגשנו בעיה שנראית מסובכת במבט ראשון, וגילינו שהיא ניתנת לפתרון אלגנטי על ידי שני צעדים פשוטים:

1. מיון המרווחים לפי נקודת ההתחלה.
2. מעבר לינארי שממזג חפיפות תוך כדי התקדמות.

בדרך למדת:

• לפתח אינטואיציה ויזואלית באמצעות ציור על ציר המספרים.
• לפרק בעיה למרכיבים בסיסיים (מיון + מיזוג).
• לזהות חפיפה באמצעות התנאי:
  max(startA, startB) ≤ min(endA, endB).

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

אתגרים דומים, כוללים: Meeting Rooms לבדיקה אם ניתן לתזמן את כל הפגישות בלי חפיפה, Employee Free Time למציאת פרקי הזמן הפנויים המשותפים בין כמה עובדים, Insert Interval בו התמקדנו במדריך קודם.

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

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

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

חידה תכנותית: מציאת הפריטים הקרובים ביותר לערך מטרה בתוך מערך

אתגר תכנותי: איזה מספר חסר

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

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

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