פורסם ב זה רק קוד, מתכוננות לראיונות

איחוד פגישות

פורסם בתאריך מאת Maya Gershovitz Bar
קוד: merge_meetings.py
זמן קריאה: 9 דקות

נתונה רשימה של אובייקטים מסוג Meeting.
כל אובייקט מתאר פגישה, ומכיל זמן התחלה וזמן סיום. זמני ההתחלה והסיום הם מספר הבלוקים של חצי שעה אחרי 9 בבוקר.
כלומר, פגישה שמתחילה ב-10 ונגמרת ב-12 תהיה (Meeting(2,6 ופגישה שמתחילה ב-12 ונגמרת ב-13:30 תהיה (Meeting(6,9.
המשימה היא לכתוב פונקציה שמקבלת רשימה לא ממוינת של פגישות ומאחדת אותן כך שכל הפגישות שחופפות בזמנים יאוחדו לפגישה אחת.

השאלה הזו אפילו באה עם דוגמא – 

arr = [Meeting(0, 1), Meeting(3, 5), Meeting(4, 8), Meeting(10, 12), Meeting(9, 10)] merge_meetings(arr) = [Meeting(0, 1), Meeting(3, 8), Meeting(9, 12)]

כמו תמיד, אני אתחיל עם הפתרון הנאיבי.

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

הסיבוכיות של הפתרון הזה היא (O(NlogN, והאינטואיציה שלי אומרת שאפשר למצוא לשאלה הזו פתרון טוב יותר, אז אני אמשיך לחפש.

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

מה הייתי יכולה לעשות אם הייתי יודעת שהפגישות לא יכולות לחפוף אלא רק להתחיל ולהסתיים באותו הזמן?

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

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

def merge_meetings(arr):
	mettings_by_times = dict()
	for current_meeting in arr:
		start = current_meeting.start_time
		end = current_meeting.end_time
		meeting_before = mettings_by_times.pop(start)
		meeting_after = mettings_by_times.pop(end)
		if meeting_before:
			new_start = meeting_before.start_time
		else:
			new_start = start
		if meeting_after:
			new_end = meeting_after.end_time
		else:
			new_end = end

		new_meeting = Meeting(new_start,new_end)
		mettings_by_times[new_start] = new_meeting
		mettings_by_times[new_end] = new_meeting
	return set(mettings_by_times.values())

מגניב, יש לי פתרון שמאחד פגישות שמתחילות/מסתיימות באותו זמן בעזרת hash table בסיבוכיות לינארית – אני עוברת על כל איבר פעם אחת, ומוציאה פגישות שאני מרחיבה, כך שבסוף הריצה יש לי לכל היותר 2N איברים בטבלה.

אבל איך אני מרחיבה את הפתרון הזה לכלול גם פגישות חופפות?

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

אז מה אני כן יכולה לעשות?

אולי אני יכולה לשמור את הפגישות בטבלה לפי מפתח אחר – לא לפי שעת התחלה ושעת סיום, אלא לפי טווחים?
כשאני חושבת על טווחים, אני ישר חושבת על עצים.

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

def inset_to_balanced_tree(t, new_meeting, node):
	if len(t) == 0:
		t.insert(new_meeting)
	if new_meeting.start_time > node.val.end_time:
		inset_to_balanced_tree(t, new_meeting, node.right_child)
	elif new_meeting.end_time > node.val.start_time:
		inset_to_balanced_tree(t, new_meeting, node.left_child)
	else:
		update_meeting(t, new_meeting, node.val)

def update_meeting(t, old_meeting, new_meeting):
	t.remove(old_meeting)
	min_start_time = min(new_meeting.start_time, old_meeting.start_time)
	max_end_time = max(new_meeting.end_time, old_meeting.end_time)
	inset_to_balanced_tree(t, Meeting(min_start_time, max_end_time), t.root)

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

נשאלת השאלה מה אני יכולה להרוויח מהגישה הזו? הרי הכנסה והוצאה מהעץ נעשית ב-logN, כך שהסיבוכיות של כל האלגוריתם היא (O(NlogN, כמו הפתרון הנאיבי שלי.

ובכן, במקרה הגרוע, שבו אין פגישות חופפות, ומערך התוצאה בעצם זהה למערך ההתחלתי אז כן, הסיבוכיות תהיה (O(NlogN. אבל במקרה שבו חלק מהפגישות מתאחדות סך האיברים בעץ יהיה קטן יותר, והסיבוכיות של האלגורית תהיה (O(NlogK. למשל, במצב שבו כל הפגישות חופפות ומתאחדות לפגישה אחת אז K=1 והסיבוכיות תהיה לינארית.

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

def merge_meetings(arr):
	if len(arr) <= 1:
		return arr
	t = RedBlackTree()
	for i in range(0,len(arr)):
		inset_to_balanced_tree(t, arr[i], t.root)

	return t.walk()

הגיע הזמן להריץ דוגמא, אני אתחיל מדוגמא קטנה – 

arr = [Meeting(1,3), Meeting(0,2)]
 merge_meetings(arr):
     t = []
     i=0
     call inset_to_balanced_tree(t, Meeting(1,3), None)
 inset_to_balanced_tree(t, Meeting(1,3), None):
     t = [Node(Meeting(1,3))]
 merge_meetings(arr):
     i=1
     call inset_to_balanced_tree(t, Meeting(0,2), Node(Meeting(1,3))
 inset_to_balanced_tree(t, Meeting(0,2), Node(Meeting(1,3)):
     Meeting(0,2).start_time > Meeting(1,3).end_time → False
     Meeting(0,2).end_time < Meeting(1,3).start_time → False
     call update_meeting(t, Meeting(0,2), (Meeting(1,3))
 update_meeting(t, Meeting(0,2), (Meeting(1,3)):
     t = []
     min_start_time = 0
     max_end_time = 3
     t = [Node(Meeting(0,3))]
return [Meeting(0,3)]

מגניב, זה עבד!

עכשיו אני אנסה לחשוב על דוגמא עם מקרה קצה – למשל דוגמא שבה לעץ הבא – 

תיכנס פגישה חדשה – (Meeting(2,4.

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

arr = [Meeting(0,2), Meeting(3,4), Meeting(2,4)]
 merge_meetings(arr):
     t = []
     t = [Node(Meeting(0,2))]
     i=1
     call inset_to_balanced_tree(t, Meeting(3,4), Node(Meeting(0,2))
 inset_to_balanced_tree(t, Meeting(3,4), Node(Meeting(0,2)):
     Meeting(3,4).start_time > Meeting(0,2).end_time → True
     call inset_to_balanced_tree(t,Meeting(3,4), None)

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

def inset_to_balanced_tree(t, new_meeting, node):
	if len(t) == 0:
		t.insert(new_meeting)
	if new_meeting.start_time > node.val.end_time:
		if node.right_child:
			inset_to_balanced_tree(t, new_meeting, node.right_child)
		else:
			node.right_child = Node(new_meeting)
	elif new_meeting.end_time < node.val.start_time:
		if node.left_child:
			inset_to_balanced_tree(t, new_meeting, node.left_child)
		else:
			node.left_child = Node(new_meeting)
	else:
		update_meeting(t, new_meeting, node.val)

אחלה, אני אריץ את הדוגמא מהתחלה – 

arr = [Meeting(0,2), Meeting(3,5), Meeting(2,4)]
 merge_meetings(arr):
     t = []
     i=0
     call inset_to_balanced_tree(t, Meeting(0,2), None)
 inset_to_balanced_tree(t, Meeting(0,2), None):
     t = [Node(Meeting(0,2))]
 merge_meetings(arr):
     i=1
     call inset_to_balanced_tree(t, Meeting(3,5), Node(Meeting(0,2))
 inset_to_balanced_tree(t, Meeting(3,5), Node(Meeting(0,2)):
     Meeting(3,4).start_time > Meeting(0,2).end_time → True
     t = [Node(Meeting(0,2)), Node(Meeting(3,5))]
 merge_meetings(arr):
     i=2
     call inset_to_balanced_tree(t, Meeting(2,4), Node(Meeting(0,2))
 inset_to_balanced_tree(t, Meeting(2,4), Node(Meeting(0,2)):
     Meeting(2,4).start_time > Meeting(0,2).end_time → False
     Meeting(2,4).end_time  Meeting(3,5).end_time → False
     Meeting(0,4).end_time < Meeting(3,5).start_time → False
     call update_meeting(t, Meeting(0,4), (Meeting(3,5))
 update_meeting(t, Meeting(0,4), (Meeting(3,5))
     t = []
     min_start_time = 0
     max_end_time = 5
     call inset_to_balanced_tree(t, Meeting(0,5), None)
 inset_to_balanced_tree(t, Meeting(0,5), None):
     t = [Node(0,5)]
 merge_meetings(arr):
     return Meeting(0,5)

אוקי, מה התוצאות שלי מהבדיקה הזו?

קודם כל, קיבלתי תוצאה נכונה, אז מגניב לדעת שהאלגוריתם עובד.
שנית כל, אני רואה שבמקום להוסיף את האיבר האחרון לעץ בהכנסה אחת, אני עשיתי את זה ב-2 הכנסות והוצאות, כי גרמתי לאיחוד של שתי פגישות. האם זה אומר שבמקרה של עץ גבוה יותר הייתי עושה logK הכנסות והוצאות? התשובה היא לא, כי פגישה חדשה יכולה לכל היותר לחפוף לשתי פגישות (אם היא הייתה חופפת ליותר מ-2 פגישות, אז לפחות שתיים מהן היו צריכות לחפוף אחת לשנייה וכבר להיות מאוחדות). כלומר, זמן ההכנסה שלי לעץ היא עדיין בסדר גודל של logK.

מעולה, הגיע הזמן לקודד!

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

המסקנות שלי מהמקרה הזה –

  1. הרבה פעמים הפתרון הנאיבי שלי הוא הפתרון הטוב ביותר, שלאו דווקא יעלה באופן אוטמטי לכולם, אז חשוב לציין אותו, עם הסתייגויות, אבל מהר ובביטחון.
  2. תמיד לשאול בראיון אם אני צריכה לשפר עוד את האלגוריתם או להתחיל לקודד, כדי לא לבזבז זמן על שיפורים אם כבר הגעתי לתוצאה האופטימלית.
  3. יש מצב שהשיפור של הפתרון שלי מ-(O(NlogN ל-(O(NloK הוא שולי מדי ולא שווה את האקסטרה מאמץ וקוד, ואני מקבלת את הטענה הזו. אחד היתרונות המהותיים שאני יכולה לחשוב עליו לפתרון שלי הוא שהוספה של פגישות חדשות נעשית ב-(O(logK, ובעוד שבפתרון הנאיבי ההוספה של פגישות חדשות נעשית ב-(O(N, אז גם פה יש שיפור מסוים. אבל אין ספק שהוא דורש הרבה מאמץ, ושווה יותר בתור פיצ’ר של העץ עצמו מאשר למטרה המקורית שלשמה העליתי אותו.
  4. אני יכולה להסתכל על המקרה הזה כאילו אני מסתבכת יותר מדי, אבל אני בוחרת להסתכל עליו כאילו מגיעות לי שאלות מעניינות יותר!

כך או כך, אני אקודד את הפתרון הנאיבי שלי עכשיו.

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/merge_meetings.py

מאת:

השאר תגובה