Car Fleet
מכוניות נוסעות בכביש חד-נתיבי לעבר מייל target. מכונית i מתחילה במייל position[i] ונוסעת במהירות של speed[i] מייל לשעה. שום מכונית אינה יכולה לעקוף מכונית אחרת: מכונית שמשיגה מכונית איטית יותר נשארת ממש מאחוריה, ומאותו רגע השתיים נוסעות יחד במהירות האיטית יותר כשיירה אחת.
גם מכונית יחידה נחשבת לשיירה, ומכונית שמגיעה לשיירה בדיוק ביעד מצטרפת אליה. החזירו את מספר השיירות שמגיעות ליעד.
פונקציה
- targetinteger
- המייל שאליו כל מכונית נוסעת
- positioninteger-array
- המייל ההתחלתי של כל מכונית
- speedinteger-array
- המהירות של כל מכונית, במיילים לשעה
- מחזירהinteger
- מספר הציים שמגיעים ליעד
אילוצים
n == position.length == speed.length1 ≤ n ≤ 1041 ≤ target ≤ 1060 ≤ position[i] < target1 ≤ speed[i] ≤ 106- כל המיקומים שונים.
דוגמאות
- קלט
- target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
- פלט
- 2
- הסבר
- למכוניות שנמצאות בקילומטרים 17, 14, 8 ו־2 נדרשות 3, 2, 3 ו־3 שעות, בהתאמה, ולכן המכונית שבקילומטר 14 משיגה את זו שבקילומטר 17, ושתי האחרות מגיעות אליהן בקילומטר 20. המכונית שבקילומטר 0 זקוקה ל־10 שעות ומגיעה לבדה.
- קלט
- target = 9position = [0, 4, 7]speed = [1, 2, 3]
- פלט
- 3
- הסבר
- המכוניות במיילים 7, 4 ו-0 זקוקות ל-2/3, 5/2 ו-9 שעות. כל אחת תגיע אחרי המכונית שלפניה, ולכן אף אחת לא תתפוס אף אחת:
3שיירות.
- קלט
- target = 10position = [3]speed = [5]
- פלט
- 1
- הסבר
- מכונית אחת בכביש היא צי אחד.
שאלת המשך
המיקומים הם מספרים שלמים קטנים מ־target. האם תוכל לספור את הציים בזמן O(n + target), בלי להשתמש במיון השוואתי?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
המכוניות לעולם לא יכולות לשנות את הסדר. עבור כל מכונית, חשבו מתי היא הייתה מגיעה ליעד אילו הכביש היה ריק. מה קובע אם היא תצליח אי פעם להשיג את המכונית שלפניה?
מתחילים מהמכונית הקרובה ביותר ליעד ומתקדמים לאחור. מכונית מצטרפת לצי שמלפניה אם היא תגיע לא יאוחר ממנו; אחרת היא יוצרת צי חדש.
מיינו לפי מיקום, מהגדול לקטן, והשאירו את הציים בערימה כשהאחרון נמצא למעלה. השוו את הזמנים
d1/s1ו־d2/s2באמצעותd1 × s2מולd2 × s1, במספרים שלמים בני 64 סיביות.
פתרון
בנתיב אחד המכוניות לעולם אינן משנות את הסדר, ומה שקובע הכול הוא מתי כל מכונית הייתה מגיעה לבדה: (target - position[i]) / speed[i]. עוברים על המכוניות מהקרובה ביותר ליעד לאחור. מכונית מתחילה צי חדש רק אם היא הייתה מגיעה מאוחר יותר מהצי שלפניה.
בדוק כל מכונית שלפניך
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מכונית מובילה שיירה בדיוק כאשר כל מכונית שלפניה הייתה מגיעה לבדה מוקדם ממנה. אם מכונית כלשהי שלפניה הייתה מגיעה לא מוקדם יותר, המכונית שלך תדביק אותה, או את השיירה שלה, עד היעד. אם כולן מגיעות מוקדם יותר, שום דבר מלפנים לא יכול לעכב אותה, כי שיירה מגיעה בזמן המאוחר ביותר מבין זמני ההגעה של מכוניותיה כשהן נוסעות לבדן. ספור את המכוניות המובילות, תוך השוואה מדויקת של הזמנים באמצעות כפל בהצלבה.
כל מכונית סורקת את כל n המכוניות: 10^8 בדיקות עבור n = 10^4.
אלגוריתם
- הגדר את
fleets = 0. - עבור כל מכונית
i, בדוק כל מכוניתjשעבורהposition[j] > position[i]. - אם יש
jשעבורה מתקיים(target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], המכוניתiנתפסת: דלג עליה. - אחרת, המכונית
iמובילה שיירה: הוסף 1 ל-fleets. - החזר את
fleets.
def carFleet(target, position, speed):
n = len(position)
fleets = 0
for i in range(n):
dist = target - position[i]
caught = False
for j in range(n):
# Car j is ahead and would not arrive before car i: car i catches it.
# (target - position[j]) / speed[j] >= dist / speed[i], without division.
if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
caught = True
break
if not caught:
fleets += 1
return fleetsמיין לפי מיקום וערום את הציים
האינטואיציה
בסדר לפי המיקום, כשהקרוב ביותר ליעד ראשון, המכוניות שלפני המכונית הנוכחית הן בדיוק אלה שכבר ראינו, שכבר נמצאות בשיירות. שמרו את השיירות במחסנית, וכל אחת מהן נשמרת כמרחק וכמהירות של המכונית הקדמית שלה, שקובעים את זמן ההגעה של השיירה.
רק האיבר העליון חשוב. כל הוספה למחסנית מגיעה строго מאוחר יותר מהשיירה שמתחתיה, כך שהזמנים עולים מלמטה למעלה, וזמן מאוחר מזה של האיבר העליון מאוחר מזה של כל מכונית שלפניה.
בדוגמה 1, לפי הסדר, המכוניות נמצאות במיקומים 17, 14, 8, 2 ו-0, והמרחק חלקי המהירות הוא 3/1, 6/3, 12/4, 18/6, 20/2. הוסיפו (3, 1). המכונית במיקום 14 מצטרפת, כי 6 × 1 > 3 × 3 אינו נכון. המכונית במיקום 8 מגיעה לאותו זמן, 12 × 1 = 3 × 4, ומצטרפת, וכך גם המכונית במיקום 2. עבור המכונית במיקום 0, 20 × 1 > 3 × 2: הוסיפו למחסנית.
אלגוריתם
- מיינו את האינדקסים של המכוניות לפי מיקום, מהגדול לקטן.
- התחילו עם מחסנית ריקה של ציי מכוניות.
- עבור כל מכונית, חשבו
dist = target - position[i]. - אם המחסנית ריקה או
dist × topSpeed > topDist × speed[i], דחפו את(dist, speed[i]); אחרת, המכונית מצטרפת לצי העליון. - החזירו את גודל המחסנית.
def carFleet(target, position, speed):
# Visit the cars from the one closest to the target backward.
order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
# One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
stack = []
for i in order:
dist, spd = target - position[i], speed[i]
# dist / spd > top_dist / top_spd, compared without division:
# this car arrives after the fleet ahead, so it never catches it.
if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
stack.append((dist, spd))
return len(stack)
מלכודות ומקרי קצה
- התייחסות לשוויון מדויק כאל צי חדש. המכוניות במיילים 8 ו-2 בדוגמה 1 מגיעות לצי במייל 20 ומצטרפות אליו. דחפו רק כאשר הזמן מאוחר יותר במובהק.
- גלישה בחישוב המכפלה הצולבת.
10^6 × 10^6 = 10^12לא נכנס ב-32 סיביות: ב-Java, ב-C, ב-C++, ב-C# וב-Rust, הרחיבו ל-64 סיביות לפני הכפל; ב-R, השתמשו במספרים ממשיים. - מיון בכיוון הלא נכון. התחלה מהמכונית הרחוקה ביותר מהיעד משווה כל מכונית למכוניות שמאחוריה, שלעולם אינן יכולות לחסום אותה.
- מיון של
positionבפני עצמו. מיינו אינדקסים, או זוגות של (position, speed), כך שכל מהירות תישאר עם המכונית שלה.
שאלות נפוצות3
מהי סיבוכיות הזמן של Car Fleet?
מיון לפי מיקום דורש O(n log n), והמעבר עם מחסנית דורש O(n), כך שהסך הכול הוא זמן O(n log n) וזיכרון O(n). בדיקת כל מכונית מול כל מכונית שלפניה דורשת O(n²).
למה Car Fleet משתמשת במחסנית?
כשעוברים על המכוניות מהחזית, צריך להשוות כל מכונית חדשה רק לצי שנמצא ממש לפניה, זה שנוצר לאחרונה. מחסנית שומרת את הצי הזה למעלה. מכיוון שקוראים רק את האיבר העליון, אפשר להשתמש גם בשני משתנים; המחסנית גם משאירה בידיך את הציים עצמם.
איך משווים זמני הגעה בלי נקודה צפה?
זמן הגעה הוא dist / speed. מכיוון שהמהירויות חיוביות, d1 / s1 > d2 / s2 מתקיים בדיוק כאשר d1 × s2 > d2 × s1. שני האגפים הם מספרים שלמים עד 10^12, לכן יש לחשב אותם בסוג נתונים של 64 סיביות, וההשוואה מדויקת, כך שאין צורך להתחשב בעיגול.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def carFleet(target, position, speed):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
target = 20 position = [14, 2, 8, 17, 0] speed = [3, 6, 4, 1, 2]
הפלט הצפוי
2