سرفصل‌ها درس 140 از 148 · ده در و جعبه‌ابزار میدانی
ده در و جعبه‌ابزار میدانی

نهایی 2: یک پنجره برای هر سرور

هوش مصنوعی خاموش این یک آزمون نهایی است، هماهنگ با آزمون پایه‌ای که در ماژول نخست دادید: همان مهارت روی مسئله‌ای متفاوت با همان دشواری، پس قاعده‌هایش را از نو بخوانید (کد پایهٔ شما منتقل نمی‌شود). مربی خاموش است و هیچ راهنمایی‌ای نیست. تنها کار کنید. دوره در درس بعد آن را کنار آزمون پایهٔ شما می‌گذارد.

یک تیم عملیات پنجره‌ای لازم دارد که هر سرور یک خوشه بیکار باشد، تا همه را با هم وصله کند. بایگانی هر سرور پنجره‌هایی را که بیکار بوده ثبت می‌کند، و بایگانی برای هر مدخل خوانده‌شده هزینه می‌گیرد. بایگانی‌ها سال‌ها به عقب می‌روند.

یک مثال کوچک

from creative.budget import Tape
idle = [[(0, 10), (30, 60), (90, 10**9)],     # server A
        [(0, 40), (50, 10**9)],               # server B
        [(20, 10**9)]]                        # server C
maintenance_window([Tape(s) for s in idle], 0, 10)   # -> 30  (A and B idle from 30 to 40, C from 20)
maintenance_window([Tape(s) for s in idle], 0, 15)   # -> 90  (B is busy from 40 to 50, A from 60 to 90)
maintenance_window([Tape(s) for s in idle], 55, 5)   # -> 55  (55 + 5 = 60: touching the end is fine)
نوبت شما

maintenance_window(servers, after, length) را بنویسید. servers فهرستی از Tapeهاست، یکی برای هر سرور. هر کدام پنجره‌های بیکار آن سرور را به‌صورت جفت‌های دقیقهٔ (start, end) نگه می‌دارد، مرتب بر اساس start، که هرگز هم‌پوشانی ندارند یا به هم نمی‌چسبند (میان دو پنجره سرور مشغول است). یک پنجره از start تا end (بدون خودش) بیکار است، و آخرین پنجرهٔ هر سرور در 10**9 تمام می‌شود، پس همیشه پاسخی هست. زودترین دقیقهٔ t >= after را برگردانید که هر سرور برای کل [t, t + length) بیکار باشد.
بودجه: 50 سرور با حدود 2,000 پنجره هر کدام (حدود 100,000 مدخل)، و after معمولاً ماه‌ها درون داده است. یک جست‌وجو در مجموع می‌تواند حداکثر 10,000 مدخل بخواند. len() یک Tape رایگان است. یک Tape مانند یک فهرست فقط‌خواندنی رفتار می‌کند (اندیس‌زدن، برش و حلقه‌زدن همه کار می‌کنند)، و هر مدخلی که به شما می‌دهد یک خواندن حساب می‌شود.

هوش مصنوعی خاموش: در این یکی مربی، راهنمایی یا راه‌حل کاملی نیست. فقط فکر خودتان.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.