והפעם נדבר על שאלת 3161. LeetCode - Block Placement Queries הבאה:
נתון לפנינו: ציר קו באורך אין סופי, שמתחיל ב 0 וממשיך ב 1,2,3 וכולי עד אין סוף.
כמו כן נותנים לנו רשימה של שאילתות, שמורכבת מ 2 סוגים של שאילתות:
סוג 1 של שאילתה, אומר לנו לשים "מחסום" בנקודה X בקו שלנו.
סוג 2 של שאילתה, שואל אותנו, האם ניתן לשים על הציר שלנו, "בלוק" ברוחב כלשהו, החל מ 0 ועד לנקודה X כלשהי. כאשר המחסומים שהצבנו בגלל שאילתה מספר 1, מגבילים את היכולת שלנו לשים "בלוקים" במיקום של המחסומים.
שאילתה מסוג 1, מוצגת כך:
queries[i] = [1, x]
כאשר הספרה הראשונה היא 1, זה אומר שמדובר על שאילתה מסוג 1, שאומרת לנו להציב מכשול במקום X כנ"ל. הבהרה: המכשול עצמו תופס 0 מקום.
לדוגמה:
queries[i] = [1, 10]
פירושו, תציב מכשול בנקודה 10 על ציר המספרים. כאשר המכשול עצמו לא תופס מקום.
![]()
שאילתה מסוג 2 מוצגת כך:
queries[i] = [2, x, sz]
כאשר הספרה הראשונה היא 2, זה אומר שמדובר על שאילתה מסוג 2, ששואלת אותנו, האם ניתן להציב בלוק ברוחב SZ עד למיקום X
לדוגמה:
queries[i] = [2, 5, 6]
השאילתה שואלת אותנו, האם ניתן להציב בלוק ברוחב 6, החל ממיקום 0 ועד למיקום 5. והתשובה היא, שלא. כי עד למיקום 5, ניתן להציב אך ורק בלוק עד רוחב 5 אך לא יותר מכך.
![]()
או לדוגמה:
queries[i] = [2, 5, 3]
השאילתה שואלת אותנו, האם ניתן להציב בלוק ברוחב 3, החל ממיקום 0 ועד למיקום 5. והתשובה היא, שכן. כי עד למיקום 5, ניתן להציב כל בלוק עד רוחב 5.
![]()
ואם לדוגמה אמרנו לנו את זה
queries[0] = [1, 10]
queries[1] = [2, 15, 12]
אז השאילתה הראשונה תאלץ אותנו לשים מכשול במקום 10 על גבי הציר. כך:
![]()
ואז לא נוכל לשים מכשול ברוחב 12, עד למיקום 15. כי המכשול שנמצא במיקום 10, מגביל אותנו לשים מכשול ברוחב 12 החל ממיקום 0, כי המכשול יתנגש במחסום שיש במיקום 10.
![]()
ואם עכשיו ישאלו אותנו:
queries[2] = [2, 10, 9]
דהיינו, האם עד מקום 10, ניתן לשים מכשול ברוחב 9, התשובה תהיה שכן
וגם אם ישאלו
queries[3] = [2, 10, 10]
דהיינו, האם עד מקום 10, ניתן לשים מכשול ברוחב 10, התשובה תהיה שכן
כך:
![]()
ואם עכשיו יגדירו לנו
queries[4] = [1, 7]
דהיינו, יבקשו מאיתנו לשים מכשול נוסף גם במקום 7, כך:
![]()
הרי שאם ישאלו אותנו עכשיו שוב פעם לדוגמה את זה:
queries[5] = [2, 10, 10]
דהיינו, האם עד מקום 10, ניתן לשים מכשול ברוחב 10, התשובה תהיה שלא. כי מאחר שכבר יש מכשול במקום 7, אז לא ניתן לשים בלוק עד מקום 10
כך:
![]()
דהיינו, מה שהיה אפשרי קודם, לשים בלוק ברוחב 10 עד מיקום 10, כי המכשול שנמצא ב 10, לא תופס מקום כנ"ל. ולכן קודם זה כן היה אפשרי. אבל כרגע בגלל שכבר יש מכשול במקום 7, הרי שלא ניתן לשים מכשול ברוחב 10, עד מיקום 10.
חידוד: הצבת המחסומים היא מצטברת. ולכן יתכן שאותה שאילתה מסוג 2, פעם אחת תהיה אפשרית ולאחר מכן היא לא תהיה יותר אפשרית, מאחר שהוגבלנו על ידי הצבת מחסום כלשהו.
ובהינתן לדוגמה הגדרת המכשולים האלו:
![]()
אז אם נשאל, האם ניתן ממקום 0 ועד מקום 17, לשים מכשול ברוחב 5? התשובה תהיה שכן, כי ניתן לשים את המכשול, בטווח שבין 3 לבין 9 כך:
![]()
אז מה בעצם שואלים אותנו?
אז השאלה הולכת כך: נותנים לנו רשימה של שאילתות, חלקן מסוג 1, דהיינו, שאילתות שמגדירות לנו היכן למקם מחסומים. כמו כן חלק מהשאילתות, הן מסוג 2, דהיינו, הן שואלות אותנו, האם בהתאם למחסומים שהצבנו עד כה על גבי ציר המספרים, האם עד כה ניתן למקום את הבלוק ברוחב מוגדר כלשהו, עד למיקום X כלשהו.
כאשר כל שאילתה מסוג 2, עומדת בפני עצמה. דהיינו, לצורך העניין אחרי שמציבים בלוק ברוחב כלשהו, מסירים אותו. והוא לא מגביל את הצבת הבלוק הבא.
וכנ"ל, הצבת המחסומים היא מצטברת. ולכן יתכן שאותה שאילתה מסוג 2, פעם אחת תהיה אפשרית ולאחר מכן היא לא תהיה יותר אפשרית, מאחר שהוגבלנו על ידי הצבת מחסום כלשהו.
ובעצם השאלה היא, בהינתן לנו רשימת שאילתות, עלינו להחזיר תשובה של: אפשרי או לא אפשרי, עבור כל אחת מהשאילתות מסוג 2 כנ"ל.
ולכאורה, זאת התשובה לשאלת הליטקוד הזאת, היא מאוד מאוד מאוד פשוטה. כי בתכלס, אפשרי לקחת נייר ולרשום את כל המחסומים. וכאשר שואלים אותנו, האם ניתן להציב בלוק ברוחב כלשהו, עד למיקום X, בסך הכל נצטרך לבדוק מ 1 ועד X, האם יש את הרוחב הרצוי להצבת הבלוק.
כך שמצד האמת, התשובה לשאלת ליטקוד הזאת היא מאוד פשוטה. אז מהי בעצם השאלה? ולמה השאלה הזאת, נחשבת לשאלת ליטקוד מאוד מאוד קשה?
והתשובה היא, שעיקר השאלה היא, איך לעשות את החישובים הנ"ל בצורה יעילה. כי לבדוק בכל פעם של שאילתה מסוג 2, החל מ 1 ועד X, האם קיים רוחב SIZE כלשהו, זה פתרון שבמאה אחוז עובד, אבל ממש לא יעיל.
למה הוא לא יעיל? ממגוון רחב מאוד של סיבות. כי נניח שישאלו אותנו, האם ניתן להציב עד מיקום 100,000,000 בלוק ברוחב 13,522. ונניח שעד מיקום 100,000,000 יש לנו 9,999 מכשולים במקומות שונים. האם באמת הגיוני שאנחנו נצטרך עכשיו לספור 100,000,000 מקומות, כדי לדעת אם אפשרי או לא אפשרי להציב את המכשול ברוחב SIZE עד למיקום X? זה כנראה מתיש ולא יעיל...
ולכן מהות השאלה היא, מהי הדרך היעילה ביותר כדי לתת תשובה לשאילתה מסוג 2. זאת מהות השאלה.
אז חלק גדול מהפתרונות שהוצעו לשאלה הזאת, עובדים עם לוגיקה של segment tree. דהיינו, מבנה נתונים מסוג "עץ מקטעים" ולא ניכנס כאן כרגע לכיוון הזה של הפתרון. אבל אני כן אציג בדרך של מחויב ואפשרי, מה בטוח נכון, לחלק לחלקים וכולי, כיצד ניתן לפתור את השאלה הזאת...
אז איך ניגשים לשאלה הזאת? איך מנסים למצוא פתרון יותר יעיל לשאלה הזאת.
אז נתחיל בפתרון הכי לא יעיל שיש וממנו ננסה לשפר. אז מהו הפתרון הכי לא יעיל. הפתרון הכי לא יעיל יהיה, שעלינו לעבור מיקום מיקום, החל מ 1 ועד X, ולנסות למצוא SIZE מקומות פנויים בלי מכשולים באמצע. כאשר אם הגענו למכשול ועדיין לא הגענו לרוחב SIZE, אז עלינו להתחיל את הספירה של המיקומים מחדש. עד שנגיע למספר X או עד שנמצא מיקומים ברוחב SIZE פנויים. ואז נוכל לדעת אם אפשרי או לא אפשרי להכניס בלוק ברוחב SIZE עד למיקום X.
ובמילים אחרות, הפתרון הכי לא יעיל, יהיה לעבור מיקום מיקום אחד אחד מההתחלה ועד X כנ"ל.
ואיך ניתן לשפר את הפתרון הזה בדרך יחסית יעילה?
נוכל לשאול את עצמנו, מה בטוח נכון. דהיינו, בכל פעם שיגדירו לנו לשים מכשול במיקום כלשהו, אנחנו נכתוב לנו את הרוחב הפנוי שיש בין מכשול למכשול כך:
![]()
וכך במקום לעבור מיקום מיקום ולחפש רוחב כלשהו של מקומות פנויים, פשוט נעבור על הגדלים של הטווחים שיש בין מכשול למכשול, וככה בעצם כבר חסכנו לעצמנו המון פעולות חיפוש...
אבל האם באמת זאת הדרך היעילה ביותר? האם באמת בכל פעם נצטרך לעבור על כל הטווחים של כל המכשולים, בכל פעם מחדש מההתחלה ועד X?
אז איך נתקדם מכאן?
אז אם נתבונן נראה, שבעצם אנחנו מחפשים למצוא דרך, איך נוכל בדרך הקצרה ביותר, לדעת, על מיקום כלשהו בציר המספרים שלנו, מהו הטווח הגדול ביותר שניתן להציב בתוכו בלוק ברוחב כלשהו. ואיך ניתן לעשות זאת בכמה שפחות פעולות.
לדוגמה: נניח ששואלים אותנו האם עד מיקום 1M ניתן להציב מכשול ב SIZE של 2000 כאשר יש לנו 5000 מכשולים שונים.
אז, בדרך הארוכה ביותר, היינו יכולים לעשות במקרה הגרוע ביותר 1M פעולות, כדי לעבור על כל המקומות ברשימת המספרים.
בפתרון הקודם שהצענו, הרי שאם יש לנו 5000 מכשולים, הרי שיש לנו 5000 טווחים של גדלים שבהם ניתן להכניס בלוקים ברוחב כלשהו. והרי שכך במקרה הגרוע ביותר נרוץ על 5000 מכשולים שונים, עד שנגלה אם אפשרי או לא אפשרי להכניס את הבלוק ברוחב 2000 הנדרש כנ"ל.
אבל האם זה הכרחי, לרוץ על 5000 טווחים, החל מהטווח הראשון ועד האחרון? אולי יש דרך שנוכל לסמן לנו בכל מיקום, מהו הטווח הגדול ביותר שניתן להכניס אליו בלוקים, עד אותו מיקום? האם יש אפשרות כזו? איך מבצעים אותה?
אז עקרונית, בכל פעם שנותנים לנו הגדרה של מכשול כלשהו, אנחנו יכולים לעבור על כל רשימת המיקומים, החל ממיקום 1 ועד למיקום של המכשול האחרון, ולסמן לעצמנו על כל מיקום, מה הרוחב המקסימאלי שיכול להיכנס עד אותו המיקום. לדוגמה כך:
![]()
הדרך הזאת, תהיה מאוד יעילה עבור החיפושים עצמם, כי בתוך שניה נוכל לדעת מהו הרוחב המקסימאלי שניתן להכניס עד למיקום X. החיסרון של הדרך הזה יהיה, שנצטרך לעדכן בכל פעם מחדש את כל המיקומים שמושפעים מכל מכשול חדש.
נניח בדוגמה הנ"ל, שיוסיפו לנו עוד מכשול במיקום 7, הרי שנצטרך לעדכן מחדש את כל הרשימה כך:
![]()
מה שאומר בעצם, שבדרך הפתרון הזו, אנחנו נעשה המון פעולות מסוג עדכון שיעזרנו לנו אומנם בפעולות מסוג חיפוש, אבל עדיין יקשו עלינו לעשות המון פעולות עדכון.
ונחדד, נניח שנבחר באפשרות של לשמור בכל מיקום כולל כל מיקום, את הרוחב המקסימאלי האפשרי עד לאותו מיקום, הרי שעדיין נצטרך לשאול את עצמנו, מה תהיה הדרך היעילה ביותר לעדכן את כל המיקומים בכל פעם מחדש. וזאת גם שאלה בפני עצמה.
אז אולי אפשרי שנקצר את פעולות העדכון בדרך הבאה: אולי במקום לעדכן את כל המיקומים עצמם, אולי נוכל לעדכן בכל פעם מחדש, את כל המיקומים של המכשולים בלבד, לדוגמה כך:
![]()
דהיינו, אולי ננסה לשמור על גבי כל מיקום של כל מכשול, את הרוחב המקסימאלי האפשרי שקיים עד אותו המכשול.
ונחדד, נניח שנבחר באפשרות של לשמור רק בכל מיקום של מכשול, את הרוחב המקסימאלי האפשרי עד לאותו מכשול, הרי שעדיין נצטרך לשאול את עצמנו, מה תהיה הדרך היעילה ביותר לעדכן את כל המיקומים של המכשולים בכל פעם מחדש. וזאת גם שאלה שאנחנו צריכים להתבונן בה.
אז איך בעצם ניגש לזה?
ונחדד: יש לנו כאן 2 סוגים של שאילתות. שאילת 1 של הגדרת מכשולים. ושאילתה 2 של בקשת מידע בהתאם להגדרת המכשולים.
וזה בעצם אומר, שיש לנו כאן כמה תהליכים נפרדים:
נניח לדוגמה שנתון לנו הציר הבא, עם החישובים הבאים:
![]()
אז יכולים להיות לנו כמה תהליכים, לדוגמה:
תהליך 1 - הגדרת המכשול במיקום X
לדוגמה: שים מכשול חדש במיקום 9
![]()
תהליך 2 - הגדרת טווח רוחב אפשרי מעודכן, מצד ימין ומצד שמאל של המכשול החדש
![]()
תהליך 3 - עדכון רוחב הטווח המקסימאלי בכל מיקום של מכשול כנ"ל
![]()
תהליך 4 - חישוב של האם ניתן לשים מכשול ברוחב כלשהו, עד למיקום X, בהתאם לרשימת הטווחים המקסימאלית עד לכל מכשול, כנ"ל בתהליך 3.
דהיינו, אם עכשיו לדוגמה ישאלו אותנו, האם ניתן לשים מכשול עד לנקודה 17 ברוחב 5, הרי שנצטרך לבצע את החישוב, לפי המידע שיש לנו על המכשול שנמצא במיקום 14 כנ"ל. והתשובה תהיה שכן.
או אם לדוגמה ישאלו אותנו, האם ניתן עד מיקום 12 לשים מכשול ברוחב 6, נצטרך לבצע את החישוב בהתאם למכשול שנמצא במיקום 9, והתשובה תהיה כן, כנ"ל.
וגם תהליך 4 עצמו, מורכב מכמה חלקים.
חלק 1 - לאתר את המכשול הקרוב ביותר לנקודה שעליה אנחנו נשאלים.
חלק 2 - לבצע את החישוב כדי למצוא תשובה למה ששאלו אותנו, על בסיס המידע שיש לנו על המכשול שמצאנו. (כי את המידע אנחנו שומרים על המכשול ולא על כל מיקום בפני עצמו).
ובאופן כללי יש כאן כל מיני תהליכים נוספים, כגון של:
1 - ניהול הרשימה של המכשולים
2 - לוודא שרשימת המכשולים ממויינת, בהתאם למיקומים של המכשולים על גבי הציר ולא לפי סדר ההכנסה שלהם לרשימה.
3 - לוודא שבכל מיקום של כל מכשול, נשמר עליו המידע של המיקום שלו על גבי הציר, של הטווח שלו מהמכשול שתחתיו, של הטווח המקסימאלי האפשרי עד אליו וכיו"ב.
דהיינו, יש כאן כל מיני תהליכים שונים.
כמו כן אציין, שיש כל מיני מקרי קצה, שאפשרי לפתור אותם יחסית בקלות, אבל אני בוחר שלא להתייחס אליהם כרגע.
לדוגמה, שלא משנה מה, תמיד לא תהיה אפשרות להכניס בלוק ברוחב SIZE אם הרוחב גדול מהמיקום עצמו. לדוגמה, לא ניתן להכניס בלוק ברוחב 100, עד מיקום 99 וכיו"ב.
או לדוגמה, שתמיד תהיה אפשרות להכניס בלוק ברוחב SIZE אם X גדול מהמיקום של המכשול האחרון + SIZE. לדוגמה, תהיה אפשרות להכניס מכשול ברוחב 10, למיקום 100, אם המכשול הגדול ביותר נמצא במיקום 70.
או כל מיני חישובים מהירים כאלו ואחרים, שאם יש 2 מכשולים בלבד, ברוחב כלשהו, הרי שמכך נוכל להסיק ששום רוחב לא יהיה קטן או גדול מ רוחב כלשהו וכיו"ב. לדוגמה 2 מכשולים על רוחב 1000, לא יוכלו לחסום את כל הבלוקים שהם ברוחב 100.
בקיצור, יש גם כל מיני מקרי קצה שאני לא רוצה להיכנס אליהם כרגע.
יש גם עניין של אפשרות להסיק מהשאילתות מסוג 2 הקודמות לשאילתה הנוכחית, במידה ולא היו שאילתות מסוג 1 ביניהן. לדוגמה, אם שאלו אותנו שאלה על מיקום 1000, ומיד אחר כך שאלו אותנו שוב שאלה על מיקום 1000 או אולי על מיקום 2000, אולי נוכל להסיק מהשאילתה הקודמת על השאילתה הנוכחית וכיו"ב. דהיינו, כל מיני מקרים פרטיים ולוגיקות ספציפיות.
כמו כן אני אוסיף, כי מאחר שיש כאן כל מיני תתי תהליכים, הרי שברמת העיקרון אפשרי לשקול מתי לבצע את פעולת ה עדכון של הטווח המקסימאלי האפשרי. האם לבצע אותו אחרי כל שאילתה מסוג 1. או אולי לפני כל שאילתה מסוג 2.
או אולי זה בכלל יהיה קשור למיקום של העדכון של 1, ביחס לשאילתה של 2. לדוגמה שאילתה מסוג 1 על מיקום 1000, לא תשפיע על שאילתה מסוג 2 על מיקום 500.
וזה קשור גם לכמות השאילתות מסוג 1 ומסוג 2. וגם קשור להאם השאילתות מסוג 1 רצופות אחת אחרי השניה או לא. כי לדוגמה, אפשרי אולי לבצע פעולת עדכון אחת, אחרי כמה שאילתות מסוג 1 של הצבת מכשולים.
בקיצור, יש כאן כל מיני זוויות והיבטים לתקוף את הנושא הזה.
אבל כרגע אני בוחר להתמקד בעניין של תהליך העדכון של הטווח המקסימאלי האפשרי, עד למיקום X.
דהיינו, ננסה למצוא דרך פשוטה איך אפשרי לעדכן יחסית בקלות, את כל המכשולים שהוצבו, בטווח ברוחב המקסימאלי, עד לאותו המכשול.
כאשר בעצם מהות השאלה היא, איך ניתן לחשב במיקום של מכשול X, את הרוחב המקסימאלי האפשרי עד לאותו המיקום, בדרך הקלה ביותר, לעדכן את המידע הזה.
אז איך ניגשים לזה?
אז כדי לדעת איך לפתור את הבעיה, לשם כך עלינו לנסות לחלק את הבעיה לחלקים הכי קטנים שיש, לחפש מה בטוח נכון, לנסות למצוא חוקיות, ואחר כך לנסות לחשוב על נוסחה ופתרון.
אז כמו שאמרנו כרגע ננסה להתמקד אך ורק בלנתח, איך הכי נכון לעדכן את רשימת המכשולים, במידע של מהו הטווח ברוחב המקסימאלי, עד לאותה נקודת מכשול.
כי כמו שאמרנו, יש כאן כל מיני תהליכים. ואחד התהליכים הוא, להחזיק רשימה של מהו הטווח המקסימאלי, עד לנקודה X. כדי לחסוך לנו לחפש בכל פעם מחדש מהתחלת הציר ועד ל X, את הטווח המקסימאלי. ולשם כך, נרצה להחזיק את הטווח המקסימאלי עד לנקודה X.
וכמו שאמרנו, יש אפשרות לנסות להחזיק את המידע, עבור כל הנקודות בציר גם כאלו שאין בהן מכשול כלשהו. ויש גם אפשרות לנסות להחזיק את המידע הזה, רק עבור הנקודות שבהן נמצא מכשול על גבי הציר.
ואני מפריד בין השאלות של: האם מתי כמה ולמה לעדכן את המידע של מהו הטווח המקסימאלי עד לנקודת מכשול כלשהי, לבין השאלה של איך לעדכן בצורה הכי יעילה את המידע הזה, של מהו ה MAX RANGE עד למכשול כלשהו. ומהמידע הזה, נוכל ללמוד על כל נקודה אחרת בציר, שאין בה מכשול.
כמו כן, אני עושה הפרדה בין השאלה של איך לנהל בפועל את הרשימה של המכשולים. כי גם את זה צריך לעשות, לדוגמה: צריך לוודא שהרשימה תהיה ממוינת לפי המיקום של המכשולים על גבי הציר ולא לפי סדר הצבת המכשולים. וכרגע לא נתמקד בזה, אלא רק באיך לעדכן את רשימת המכשולים.
כמו כן, אנחנו נניח שננהל את הרשימה עצמה, בתוך מבנה של רשימה פשוטה ורגילה. ולא בצורה של עץ טווחים (segment tree) שזה עוד נושא בפני עצמו.
ולכן נשאל: נניח שאנחנו רוצים לנהל רשימה של כל המכשולים בצורה של רשימה ולא של עץ או של משנה אחר. ונניח שהרשימה הזאת של המכשולים, ממוינת לפי סדר המכשולים על גבי הציר. ונניח שאנחנו רוצים בכל פעם לעדכן אותה, במידע של מהו הטווח המקסימאלי, שאפשרי להציב בלוק, החל מהתחלת הציר ועד לנקודת מכשול כלשהי, אז כיצד יהיה הכי יעיל לעשות את זה?
אז לשם כך נתחיל לחלק לחלקים לחלק הקטן ביותר, והוא כמובן יהיה ציר ריק בלי שום מכשולים כלשהם. זהו כמובן המקרה הפשוט ביותר. כך:
![]()
אז לצורך העניין נתבונן על ציר ריק ללא מכשולים, ונשאל: מהו גודל הבלוק המקסימאלי שניתן להציב עד נקודה מספר 1? תשובה: בלוק ברוחב של 1.
ועד נניח למיקום 7, איזה גודל מקסימאלי של בלוק, ניתן להציב? תשובה: 7. כי עד מיקום 7, לא ניתן להכניס בלוק יותר רחב מהרוחב של המיקום הנוכחי.
במילים אחרות, לצורך העניין ניתן לדמיין שיש לנו בלוק בנקודה 0, שמגביל אותנו לכך שלא נוכל להכניס עד נקודה X, שום מכשול שהוא יותר גדול מנקודה X.
![]()
עד כאן זה משהו שהוא הכי פשוט שיש ושהוא בטוח נכון.
ומה נוכל להסיק מכך שהוא בטוח נכון, על מקרה שהוא קצת יותר מורכב?
תשובה: מכך נוכל להסיק לגבי מקרה של ציר, שיש עליו רק מכשול 1 בלבד. לדוגמה מכשול 1 בלבד במיקום 5:
![]()
נוכל להסיק בוודאות, כי כאשר מגדירים לנו את המכשול הראשון, אנחנו יכולים לדעת בוודאות של מאה אחוז, שעד המכשול הראשון, לא ניתן להכניס שום בלוק, שהוא גדול יותר מהמיקום של המכשול הראשון.
לדוגמה: אם המכשול הראשון הוא במיקום 5, הרי שמכך נובע, שעד המכשול הראשון במיקום עד, הטווח והגודל המקסימאלי של בלוק שניתן להכניס, יהיה בגודל 5 בלבד.
ולכן מכך נובע, שכאשר יתנו לנו את המכשול הראשון, נרשום לידו, שה MAX RANGE המקסימאלי עד אליו, הוא המיקום של אותו X כנ"ל.
עכשיו נתבונן רגע אחד על המקרה הקודם, ונשאל: מה יהיה...
There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.
You are given a 2D array queries, which contains two types of queries:
For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.
For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.
Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise.
Example 1:
Input: queries = [[1,2], [2,3,3], [2,3,1], [2,2,2]]
Output: [false,true,true]
Explanation:
For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.
Example 2:
Input: queries = [[1,7], [2,7,6], [1,2], [2,7,5], [2,7,6]]
Output: [true,true,false]
Explanation:
Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7.
Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2.
אז קודם כל נסביר את השאלה שהולכת כך:You are given a 2D array queries, which contains two types of queries:
For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.
For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.
Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise.
Example 1:
Input: queries = [[1,2], [2,3,3], [2,3,1], [2,2,2]]
Output: [false,true,true]
Explanation:
For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.
Example 2:
Input: queries = [[1,7], [2,7,6], [1,2], [2,7,5], [2,7,6]]
Output: [true,true,false]
Explanation:
Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7.
Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2.
נתון לפנינו: ציר קו באורך אין סופי, שמתחיל ב 0 וממשיך ב 1,2,3 וכולי עד אין סוף.
כמו כן נותנים לנו רשימה של שאילתות, שמורכבת מ 2 סוגים של שאילתות:
סוג 1 של שאילתה, אומר לנו לשים "מחסום" בנקודה X בקו שלנו.
סוג 2 של שאילתה, שואל אותנו, האם ניתן לשים על הציר שלנו, "בלוק" ברוחב כלשהו, החל מ 0 ועד לנקודה X כלשהי. כאשר המחסומים שהצבנו בגלל שאילתה מספר 1, מגבילים את היכולת שלנו לשים "בלוקים" במיקום של המחסומים.
שאילתה מסוג 1, מוצגת כך:
queries[i] = [1, x]
כאשר הספרה הראשונה היא 1, זה אומר שמדובר על שאילתה מסוג 1, שאומרת לנו להציב מכשול במקום X כנ"ל. הבהרה: המכשול עצמו תופס 0 מקום.
לדוגמה:
queries[i] = [1, 10]
פירושו, תציב מכשול בנקודה 10 על ציר המספרים. כאשר המכשול עצמו לא תופס מקום.
שאילתה מסוג 2 מוצגת כך:
queries[i] = [2, x, sz]
כאשר הספרה הראשונה היא 2, זה אומר שמדובר על שאילתה מסוג 2, ששואלת אותנו, האם ניתן להציב בלוק ברוחב SZ עד למיקום X
לדוגמה:
queries[i] = [2, 5, 6]
השאילתה שואלת אותנו, האם ניתן להציב בלוק ברוחב 6, החל ממיקום 0 ועד למיקום 5. והתשובה היא, שלא. כי עד למיקום 5, ניתן להציב אך ורק בלוק עד רוחב 5 אך לא יותר מכך.
או לדוגמה:
queries[i] = [2, 5, 3]
השאילתה שואלת אותנו, האם ניתן להציב בלוק ברוחב 3, החל ממיקום 0 ועד למיקום 5. והתשובה היא, שכן. כי עד למיקום 5, ניתן להציב כל בלוק עד רוחב 5.
ואם לדוגמה אמרנו לנו את זה
queries[0] = [1, 10]
queries[1] = [2, 15, 12]
אז השאילתה הראשונה תאלץ אותנו לשים מכשול במקום 10 על גבי הציר. כך:
ואז לא נוכל לשים מכשול ברוחב 12, עד למיקום 15. כי המכשול שנמצא במיקום 10, מגביל אותנו לשים מכשול ברוחב 12 החל ממיקום 0, כי המכשול יתנגש במחסום שיש במיקום 10.
ואם עכשיו ישאלו אותנו:
queries[2] = [2, 10, 9]
דהיינו, האם עד מקום 10, ניתן לשים מכשול ברוחב 9, התשובה תהיה שכן
וגם אם ישאלו
queries[3] = [2, 10, 10]
דהיינו, האם עד מקום 10, ניתן לשים מכשול ברוחב 10, התשובה תהיה שכן
כך:
ואם עכשיו יגדירו לנו
queries[4] = [1, 7]
דהיינו, יבקשו מאיתנו לשים מכשול נוסף גם במקום 7, כך:
הרי שאם ישאלו אותנו עכשיו שוב פעם לדוגמה את זה:
queries[5] = [2, 10, 10]
דהיינו, האם עד מקום 10, ניתן לשים מכשול ברוחב 10, התשובה תהיה שלא. כי מאחר שכבר יש מכשול במקום 7, אז לא ניתן לשים בלוק עד מקום 10
כך:
דהיינו, מה שהיה אפשרי קודם, לשים בלוק ברוחב 10 עד מיקום 10, כי המכשול שנמצא ב 10, לא תופס מקום כנ"ל. ולכן קודם זה כן היה אפשרי. אבל כרגע בגלל שכבר יש מכשול במקום 7, הרי שלא ניתן לשים מכשול ברוחב 10, עד מיקום 10.
חידוד: הצבת המחסומים היא מצטברת. ולכן יתכן שאותה שאילתה מסוג 2, פעם אחת תהיה אפשרית ולאחר מכן היא לא תהיה יותר אפשרית, מאחר שהוגבלנו על ידי הצבת מחסום כלשהו.
ובהינתן לדוגמה הגדרת המכשולים האלו:
אז אם נשאל, האם ניתן ממקום 0 ועד מקום 17, לשים מכשול ברוחב 5? התשובה תהיה שכן, כי ניתן לשים את המכשול, בטווח שבין 3 לבין 9 כך:
אז מה בעצם שואלים אותנו?
אז השאלה הולכת כך: נותנים לנו רשימה של שאילתות, חלקן מסוג 1, דהיינו, שאילתות שמגדירות לנו היכן למקם מחסומים. כמו כן חלק מהשאילתות, הן מסוג 2, דהיינו, הן שואלות אותנו, האם בהתאם למחסומים שהצבנו עד כה על גבי ציר המספרים, האם עד כה ניתן למקום את הבלוק ברוחב מוגדר כלשהו, עד למיקום X כלשהו.
כאשר כל שאילתה מסוג 2, עומדת בפני עצמה. דהיינו, לצורך העניין אחרי שמציבים בלוק ברוחב כלשהו, מסירים אותו. והוא לא מגביל את הצבת הבלוק הבא.
וכנ"ל, הצבת המחסומים היא מצטברת. ולכן יתכן שאותה שאילתה מסוג 2, פעם אחת תהיה אפשרית ולאחר מכן היא לא תהיה יותר אפשרית, מאחר שהוגבלנו על ידי הצבת מחסום כלשהו.
ובעצם השאלה היא, בהינתן לנו רשימת שאילתות, עלינו להחזיר תשובה של: אפשרי או לא אפשרי, עבור כל אחת מהשאילתות מסוג 2 כנ"ל.
ולכאורה, זאת התשובה לשאלת הליטקוד הזאת, היא מאוד מאוד מאוד פשוטה. כי בתכלס, אפשרי לקחת נייר ולרשום את כל המחסומים. וכאשר שואלים אותנו, האם ניתן להציב בלוק ברוחב כלשהו, עד למיקום X, בסך הכל נצטרך לבדוק מ 1 ועד X, האם יש את הרוחב הרצוי להצבת הבלוק.
כך שמצד האמת, התשובה לשאלת ליטקוד הזאת היא מאוד פשוטה. אז מהי בעצם השאלה? ולמה השאלה הזאת, נחשבת לשאלת ליטקוד מאוד מאוד קשה?
והתשובה היא, שעיקר השאלה היא, איך לעשות את החישובים הנ"ל בצורה יעילה. כי לבדוק בכל פעם של שאילתה מסוג 2, החל מ 1 ועד X, האם קיים רוחב SIZE כלשהו, זה פתרון שבמאה אחוז עובד, אבל ממש לא יעיל.
למה הוא לא יעיל? ממגוון רחב מאוד של סיבות. כי נניח שישאלו אותנו, האם ניתן להציב עד מיקום 100,000,000 בלוק ברוחב 13,522. ונניח שעד מיקום 100,000,000 יש לנו 9,999 מכשולים במקומות שונים. האם באמת הגיוני שאנחנו נצטרך עכשיו לספור 100,000,000 מקומות, כדי לדעת אם אפשרי או לא אפשרי להציב את המכשול ברוחב SIZE עד למיקום X? זה כנראה מתיש ולא יעיל...
ולכן מהות השאלה היא, מהי הדרך היעילה ביותר כדי לתת תשובה לשאילתה מסוג 2. זאת מהות השאלה.
אז חלק גדול מהפתרונות שהוצעו לשאלה הזאת, עובדים עם לוגיקה של segment tree. דהיינו, מבנה נתונים מסוג "עץ מקטעים" ולא ניכנס כאן כרגע לכיוון הזה של הפתרון. אבל אני כן אציג בדרך של מחויב ואפשרי, מה בטוח נכון, לחלק לחלקים וכולי, כיצד ניתן לפתור את השאלה הזאת...
אז איך ניגשים לשאלה הזאת? איך מנסים למצוא פתרון יותר יעיל לשאלה הזאת.
אז נתחיל בפתרון הכי לא יעיל שיש וממנו ננסה לשפר. אז מהו הפתרון הכי לא יעיל. הפתרון הכי לא יעיל יהיה, שעלינו לעבור מיקום מיקום, החל מ 1 ועד X, ולנסות למצוא SIZE מקומות פנויים בלי מכשולים באמצע. כאשר אם הגענו למכשול ועדיין לא הגענו לרוחב SIZE, אז עלינו להתחיל את הספירה של המיקומים מחדש. עד שנגיע למספר X או עד שנמצא מיקומים ברוחב SIZE פנויים. ואז נוכל לדעת אם אפשרי או לא אפשרי להכניס בלוק ברוחב SIZE עד למיקום X.
ובמילים אחרות, הפתרון הכי לא יעיל, יהיה לעבור מיקום מיקום אחד אחד מההתחלה ועד X כנ"ל.
ואיך ניתן לשפר את הפתרון הזה בדרך יחסית יעילה?
נוכל לשאול את עצמנו, מה בטוח נכון. דהיינו, בכל פעם שיגדירו לנו לשים מכשול במיקום כלשהו, אנחנו נכתוב לנו את הרוחב הפנוי שיש בין מכשול למכשול כך:
וכך במקום לעבור מיקום מיקום ולחפש רוחב כלשהו של מקומות פנויים, פשוט נעבור על הגדלים של הטווחים שיש בין מכשול למכשול, וככה בעצם כבר חסכנו לעצמנו המון פעולות חיפוש...
אבל האם באמת זאת הדרך היעילה ביותר? האם באמת בכל פעם נצטרך לעבור על כל הטווחים של כל המכשולים, בכל פעם מחדש מההתחלה ועד X?
אז איך נתקדם מכאן?
אז אם נתבונן נראה, שבעצם אנחנו מחפשים למצוא דרך, איך נוכל בדרך הקצרה ביותר, לדעת, על מיקום כלשהו בציר המספרים שלנו, מהו הטווח הגדול ביותר שניתן להציב בתוכו בלוק ברוחב כלשהו. ואיך ניתן לעשות זאת בכמה שפחות פעולות.
לדוגמה: נניח ששואלים אותנו האם עד מיקום 1M ניתן להציב מכשול ב SIZE של 2000 כאשר יש לנו 5000 מכשולים שונים.
אז, בדרך הארוכה ביותר, היינו יכולים לעשות במקרה הגרוע ביותר 1M פעולות, כדי לעבור על כל המקומות ברשימת המספרים.
בפתרון הקודם שהצענו, הרי שאם יש לנו 5000 מכשולים, הרי שיש לנו 5000 טווחים של גדלים שבהם ניתן להכניס בלוקים ברוחב כלשהו. והרי שכך במקרה הגרוע ביותר נרוץ על 5000 מכשולים שונים, עד שנגלה אם אפשרי או לא אפשרי להכניס את הבלוק ברוחב 2000 הנדרש כנ"ל.
אבל האם זה הכרחי, לרוץ על 5000 טווחים, החל מהטווח הראשון ועד האחרון? אולי יש דרך שנוכל לסמן לנו בכל מיקום, מהו הטווח הגדול ביותר שניתן להכניס אליו בלוקים, עד אותו מיקום? האם יש אפשרות כזו? איך מבצעים אותה?
אז עקרונית, בכל פעם שנותנים לנו הגדרה של מכשול כלשהו, אנחנו יכולים לעבור על כל רשימת המיקומים, החל ממיקום 1 ועד למיקום של המכשול האחרון, ולסמן לעצמנו על כל מיקום, מה הרוחב המקסימאלי שיכול להיכנס עד אותו המיקום. לדוגמה כך:
הדרך הזאת, תהיה מאוד יעילה עבור החיפושים עצמם, כי בתוך שניה נוכל לדעת מהו הרוחב המקסימאלי שניתן להכניס עד למיקום X. החיסרון של הדרך הזה יהיה, שנצטרך לעדכן בכל פעם מחדש את כל המיקומים שמושפעים מכל מכשול חדש.
נניח בדוגמה הנ"ל, שיוסיפו לנו עוד מכשול במיקום 7, הרי שנצטרך לעדכן מחדש את כל הרשימה כך:
מה שאומר בעצם, שבדרך הפתרון הזו, אנחנו נעשה המון פעולות מסוג עדכון שיעזרנו לנו אומנם בפעולות מסוג חיפוש, אבל עדיין יקשו עלינו לעשות המון פעולות עדכון.
ונחדד, נניח שנבחר באפשרות של לשמור בכל מיקום כולל כל מיקום, את הרוחב המקסימאלי האפשרי עד לאותו מיקום, הרי שעדיין נצטרך לשאול את עצמנו, מה תהיה הדרך היעילה ביותר לעדכן את כל המיקומים בכל פעם מחדש. וזאת גם שאלה בפני עצמה.
אז אולי אפשרי שנקצר את פעולות העדכון בדרך הבאה: אולי במקום לעדכן את כל המיקומים עצמם, אולי נוכל לעדכן בכל פעם מחדש, את כל המיקומים של המכשולים בלבד, לדוגמה כך:
דהיינו, אולי ננסה לשמור על גבי כל מיקום של כל מכשול, את הרוחב המקסימאלי האפשרי שקיים עד אותו המכשול.
ונחדד, נניח שנבחר באפשרות של לשמור רק בכל מיקום של מכשול, את הרוחב המקסימאלי האפשרי עד לאותו מכשול, הרי שעדיין נצטרך לשאול את עצמנו, מה תהיה הדרך היעילה ביותר לעדכן את כל המיקומים של המכשולים בכל פעם מחדש. וזאת גם שאלה שאנחנו צריכים להתבונן בה.
אז איך בעצם ניגש לזה?
ונחדד: יש לנו כאן 2 סוגים של שאילתות. שאילת 1 של הגדרת מכשולים. ושאילתה 2 של בקשת מידע בהתאם להגדרת המכשולים.
וזה בעצם אומר, שיש לנו כאן כמה תהליכים נפרדים:
נניח לדוגמה שנתון לנו הציר הבא, עם החישובים הבאים:
אז יכולים להיות לנו כמה תהליכים, לדוגמה:
תהליך 1 - הגדרת המכשול במיקום X
לדוגמה: שים מכשול חדש במיקום 9
תהליך 2 - הגדרת טווח רוחב אפשרי מעודכן, מצד ימין ומצד שמאל של המכשול החדש
תהליך 3 - עדכון רוחב הטווח המקסימאלי בכל מיקום של מכשול כנ"ל
תהליך 4 - חישוב של האם ניתן לשים מכשול ברוחב כלשהו, עד למיקום X, בהתאם לרשימת הטווחים המקסימאלית עד לכל מכשול, כנ"ל בתהליך 3.
דהיינו, אם עכשיו לדוגמה ישאלו אותנו, האם ניתן לשים מכשול עד לנקודה 17 ברוחב 5, הרי שנצטרך לבצע את החישוב, לפי המידע שיש לנו על המכשול שנמצא במיקום 14 כנ"ל. והתשובה תהיה שכן.
או אם לדוגמה ישאלו אותנו, האם ניתן עד מיקום 12 לשים מכשול ברוחב 6, נצטרך לבצע את החישוב בהתאם למכשול שנמצא במיקום 9, והתשובה תהיה כן, כנ"ל.
וגם תהליך 4 עצמו, מורכב מכמה חלקים.
חלק 1 - לאתר את המכשול הקרוב ביותר לנקודה שעליה אנחנו נשאלים.
חלק 2 - לבצע את החישוב כדי למצוא תשובה למה ששאלו אותנו, על בסיס המידע שיש לנו על המכשול שמצאנו. (כי את המידע אנחנו שומרים על המכשול ולא על כל מיקום בפני עצמו).
ובאופן כללי יש כאן כל מיני תהליכים נוספים, כגון של:
1 - ניהול הרשימה של המכשולים
2 - לוודא שרשימת המכשולים ממויינת, בהתאם למיקומים של המכשולים על גבי הציר ולא לפי סדר ההכנסה שלהם לרשימה.
3 - לוודא שבכל מיקום של כל מכשול, נשמר עליו המידע של המיקום שלו על גבי הציר, של הטווח שלו מהמכשול שתחתיו, של הטווח המקסימאלי האפשרי עד אליו וכיו"ב.
דהיינו, יש כאן כל מיני תהליכים שונים.
כמו כן אציין, שיש כל מיני מקרי קצה, שאפשרי לפתור אותם יחסית בקלות, אבל אני בוחר שלא להתייחס אליהם כרגע.
לדוגמה, שלא משנה מה, תמיד לא תהיה אפשרות להכניס בלוק ברוחב SIZE אם הרוחב גדול מהמיקום עצמו. לדוגמה, לא ניתן להכניס בלוק ברוחב 100, עד מיקום 99 וכיו"ב.
או לדוגמה, שתמיד תהיה אפשרות להכניס בלוק ברוחב SIZE אם X גדול מהמיקום של המכשול האחרון + SIZE. לדוגמה, תהיה אפשרות להכניס מכשול ברוחב 10, למיקום 100, אם המכשול הגדול ביותר נמצא במיקום 70.
או כל מיני חישובים מהירים כאלו ואחרים, שאם יש 2 מכשולים בלבד, ברוחב כלשהו, הרי שמכך נוכל להסיק ששום רוחב לא יהיה קטן או גדול מ רוחב כלשהו וכיו"ב. לדוגמה 2 מכשולים על רוחב 1000, לא יוכלו לחסום את כל הבלוקים שהם ברוחב 100.
בקיצור, יש גם כל מיני מקרי קצה שאני לא רוצה להיכנס אליהם כרגע.
יש גם עניין של אפשרות להסיק מהשאילתות מסוג 2 הקודמות לשאילתה הנוכחית, במידה ולא היו שאילתות מסוג 1 ביניהן. לדוגמה, אם שאלו אותנו שאלה על מיקום 1000, ומיד אחר כך שאלו אותנו שוב שאלה על מיקום 1000 או אולי על מיקום 2000, אולי נוכל להסיק מהשאילתה הקודמת על השאילתה הנוכחית וכיו"ב. דהיינו, כל מיני מקרים פרטיים ולוגיקות ספציפיות.
כמו כן אני אוסיף, כי מאחר שיש כאן כל מיני תתי תהליכים, הרי שברמת העיקרון אפשרי לשקול מתי לבצע את פעולת ה עדכון של הטווח המקסימאלי האפשרי. האם לבצע אותו אחרי כל שאילתה מסוג 1. או אולי לפני כל שאילתה מסוג 2.
או אולי זה בכלל יהיה קשור למיקום של העדכון של 1, ביחס לשאילתה של 2. לדוגמה שאילתה מסוג 1 על מיקום 1000, לא תשפיע על שאילתה מסוג 2 על מיקום 500.
וזה קשור גם לכמות השאילתות מסוג 1 ומסוג 2. וגם קשור להאם השאילתות מסוג 1 רצופות אחת אחרי השניה או לא. כי לדוגמה, אפשרי אולי לבצע פעולת עדכון אחת, אחרי כמה שאילתות מסוג 1 של הצבת מכשולים.
בקיצור, יש כאן כל מיני זוויות והיבטים לתקוף את הנושא הזה.
אבל כרגע אני בוחר להתמקד בעניין של תהליך העדכון של הטווח המקסימאלי האפשרי, עד למיקום X.
דהיינו, ננסה למצוא דרך פשוטה איך אפשרי לעדכן יחסית בקלות, את כל המכשולים שהוצבו, בטווח ברוחב המקסימאלי, עד לאותו המכשול.
כאשר בעצם מהות השאלה היא, איך ניתן לחשב במיקום של מכשול X, את הרוחב המקסימאלי האפשרי עד לאותו המיקום, בדרך הקלה ביותר, לעדכן את המידע הזה.
אז איך ניגשים לזה?
אז כדי לדעת איך לפתור את הבעיה, לשם כך עלינו לנסות לחלק את הבעיה לחלקים הכי קטנים שיש, לחפש מה בטוח נכון, לנסות למצוא חוקיות, ואחר כך לנסות לחשוב על נוסחה ופתרון.
אז כמו שאמרנו כרגע ננסה להתמקד אך ורק בלנתח, איך הכי נכון לעדכן את רשימת המכשולים, במידע של מהו הטווח ברוחב המקסימאלי, עד לאותה נקודת מכשול.
כי כמו שאמרנו, יש כאן כל מיני תהליכים. ואחד התהליכים הוא, להחזיק רשימה של מהו הטווח המקסימאלי, עד לנקודה X. כדי לחסוך לנו לחפש בכל פעם מחדש מהתחלת הציר ועד ל X, את הטווח המקסימאלי. ולשם כך, נרצה להחזיק את הטווח המקסימאלי עד לנקודה X.
וכמו שאמרנו, יש אפשרות לנסות להחזיק את המידע, עבור כל הנקודות בציר גם כאלו שאין בהן מכשול כלשהו. ויש גם אפשרות לנסות להחזיק את המידע הזה, רק עבור הנקודות שבהן נמצא מכשול על גבי הציר.
ואני מפריד בין השאלות של: האם מתי כמה ולמה לעדכן את המידע של מהו הטווח המקסימאלי עד לנקודת מכשול כלשהי, לבין השאלה של איך לעדכן בצורה הכי יעילה את המידע הזה, של מהו ה MAX RANGE עד למכשול כלשהו. ומהמידע הזה, נוכל ללמוד על כל נקודה אחרת בציר, שאין בה מכשול.
כמו כן, אני עושה הפרדה בין השאלה של איך לנהל בפועל את הרשימה של המכשולים. כי גם את זה צריך לעשות, לדוגמה: צריך לוודא שהרשימה תהיה ממוינת לפי המיקום של המכשולים על גבי הציר ולא לפי סדר הצבת המכשולים. וכרגע לא נתמקד בזה, אלא רק באיך לעדכן את רשימת המכשולים.
כמו כן, אנחנו נניח שננהל את הרשימה עצמה, בתוך מבנה של רשימה פשוטה ורגילה. ולא בצורה של עץ טווחים (segment tree) שזה עוד נושא בפני עצמו.
ולכן נשאל: נניח שאנחנו רוצים לנהל רשימה של כל המכשולים בצורה של רשימה ולא של עץ או של משנה אחר. ונניח שהרשימה הזאת של המכשולים, ממוינת לפי סדר המכשולים על גבי הציר. ונניח שאנחנו רוצים בכל פעם לעדכן אותה, במידע של מהו הטווח המקסימאלי, שאפשרי להציב בלוק, החל מהתחלת הציר ועד לנקודת מכשול כלשהי, אז כיצד יהיה הכי יעיל לעשות את זה?
אז לשם כך נתחיל לחלק לחלקים לחלק הקטן ביותר, והוא כמובן יהיה ציר ריק בלי שום מכשולים כלשהם. זהו כמובן המקרה הפשוט ביותר. כך:
אז לצורך העניין נתבונן על ציר ריק ללא מכשולים, ונשאל: מהו גודל הבלוק המקסימאלי שניתן להציב עד נקודה מספר 1? תשובה: בלוק ברוחב של 1.
ועד נניח למיקום 7, איזה גודל מקסימאלי של בלוק, ניתן להציב? תשובה: 7. כי עד מיקום 7, לא ניתן להכניס בלוק יותר רחב מהרוחב של המיקום הנוכחי.
במילים אחרות, לצורך העניין ניתן לדמיין שיש לנו בלוק בנקודה 0, שמגביל אותנו לכך שלא נוכל להכניס עד נקודה X, שום מכשול שהוא יותר גדול מנקודה X.
עד כאן זה משהו שהוא הכי פשוט שיש ושהוא בטוח נכון.
ומה נוכל להסיק מכך שהוא בטוח נכון, על מקרה שהוא קצת יותר מורכב?
תשובה: מכך נוכל להסיק לגבי מקרה של ציר, שיש עליו רק מכשול 1 בלבד. לדוגמה מכשול 1 בלבד במיקום 5:
נוכל להסיק בוודאות, כי כאשר מגדירים לנו את המכשול הראשון, אנחנו יכולים לדעת בוודאות של מאה אחוז, שעד המכשול הראשון, לא ניתן להכניס שום בלוק, שהוא גדול יותר מהמיקום של המכשול הראשון.
לדוגמה: אם המכשול הראשון הוא במיקום 5, הרי שמכך נובע, שעד המכשול הראשון במיקום עד, הטווח והגודל המקסימאלי של בלוק שניתן להכניס, יהיה בגודל 5 בלבד.
ולכן מכך נובע, שכאשר יתנו לנו את המכשול הראשון, נרשום לידו, שה MAX RANGE המקסימאלי עד אליו, הוא המיקום של אותו X כנ"ל.
עכשיו נתבונן רגע אחד על המקרה הקודם, ונשאל: מה יהיה...
050-3331-331