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

Insert Interval LeetCode 57

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

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

• חשיבה במונחים של מקרים מפורקים (לפני / חופף / אחרי).
• שימוש באלגוריתם לינארי פשוט ואלגנטי.
• פיתוח חשיבה ויזואלית על ציר הזמן.

האתגר "הכנסת מרווח"

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

דוגמה 1:

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

דוגמה 2:

Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

איך לגשת לבעיה

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

מאיפה מתחילים?

השלבים הבאים יכולים לעזור:

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

דרך טובה להתחיל היא ציור של הטווחים על ציר זמן. אז נצייר:

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

בשלב הזה צריך להיות ברור לך שיש להבחין בין שלושה מצבים:

1. מרווחים שבאים לפני המרווח החדש (ללא חפיפה).
2. מרווחים שצריך למזג עם המרווח החדש.
3. מרווחים שבאים אחרי המרווח החדש (גם ללא חפיפה).

הפתרון

def insert_interval(intervals, new_interval):
    n = len(intervals)
    i = 0
    res = []

    # 1. Add intervals that come before the new interval
    while i < n and intervals[i][1] < new_interval[0]:
        res.append(intervals[i])
        i += 1
    
    # 2. Merge overlapping intervals into the new interval
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(intervals[i][0], new_interval[0])
        new_interval[1] = max(intervals[i][1], new_interval[1])
        i += 1
    res.append(new_interval)

    # 3. Add intervals that come after the new interval
    while i < n:
        res.append(intervals[i])
        i += 1

    return res

• שלב 1: "לפני"
  כל עוד המרווח מסתיים לפני תחילת החדש, מוסיפים אותו לרשימת התוצאה:

  while intervals[i][1] < new_interval[0]

• שלב 2: "חפיפה"
  כל עוד יש חפיפה, מאחדים את גבולות ההתחלה והסיום:

  new_interval[0] = min(...), new_interval[1] = max(...)

• שלב 3: "אחרי"
  אחרי שמזגנו, כל היתר נכנסים כמו שהם.

התוצאה תמיד תהיה ממוינת וללא חפיפות.

בדיקות

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

# Tests
test_cases = [
    [ [[1,3],[6,9]], [2,5], [[1,5],[6,9]] ],
    [ [[1,7],[6,9]], [2,5], [[1,9]] ],
    [ [[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8], [[1,2],[3,10],[12,16]] ],
]

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

for intervals, new_interval, exp_res in test_cases:
    actual_res = insert_interval(intervals, new_interval)
    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).

לסיכום

בעיות מרווחים מופיעות בפרקטיקה היומיומית: לוחות שנה, זיכרון, רשתות, עיבוד נתונים. כאשר האתגר "הכנסת מרווח", המוסבר במדריך, מלמד תבנית חשיבה שימושית: לפרק בעיה למקרים (לפני / חפיפה / אחרי) ולטפל בכל מקרה בצורה נקייה. שליטה בבעיה הזו תקל על בעיות דומות אשר עשויות להופיע בראיון הטכני למתכנת, דוגמת: Merge Intervals, Meeting Rooms, Employee Free Time ועוד.

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

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

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

אתגר תכנותי: סכום השילובים combination sum

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

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

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