Bài cuối 2: một khoảng thời gian cho mọi máy chủ
Tắt AI Đây là một bài thi cuối, được ghép với bài kiểm tra đầu vào bạn đã làm ở mô-đun đầu tiên: cùng kỹ năng trên một bài toán khác có cùng độ khó, nên hãy đọc lại các quy tắc của nó từ đầu (mã đầu vào của bạn sẽ không dùng lại được). Người hướng dẫn bị tắt và không có gợi ý nào. Hãy tự làm. Khóa học đặt nó cạnh bài kiểm tra đầu vào của bạn ở bài học tiếp theo.
Một nhóm vận hành cần một khoảng thời gian mà mọi máy chủ trong một cụm đều rảnh, để vá chúng cùng lúc. Kho lưu trữ của mỗi máy chủ ghi lại các khoảng thời gian nó rảnh, và kho lưu trữ tính tiền cho mỗi mục được lấy ra. Các kho lưu trữ có từ nhiều năm trước.
Một ví dụ nhỏ
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)Viết maintenance_window(servers, after, length). servers là một list các Tape, mỗi cái cho một máy chủ. Mỗi cái giữ các khoảng rảnh của máy chủ đó dưới dạng các cặp phút (start, end), sắp xếp theo start, không bao giờ chồng lên hay chạm nhau (giữa hai khoảng máy chủ bận). Một khoảng rảnh từ start tới nhưng không bao gồm end, và khoảng cuối cùng của mọi máy chủ kết thúc ở 10**9, nên luôn có một câu trả lời. Trả về phút sớm nhất t >= after sao cho mọi máy chủ đều rảnh trong toàn bộ [t, t + length).
Ngân sách: 50 máy chủ với khoảng 2.000 khoảng mỗi cái (khoảng 100.000 mục), và after thường nằm sâu vài tháng trong dữ liệu. Một lần tìm được đọc nhiều nhất 10.000 mục tổng cộng. len() của một Tape là miễn phí. Một Tape hoạt động như một list chỉ đọc (chỉ số, cắt lát và lặp đều hoạt động), và mỗi mục nó trao cho bạn được tính là một lần đọc.
Tắt AI: không có gia sư, gợi ý hoặc lời giải mẫu cho bài này. Chỉ dùng tư duy của riêng bạn.
Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này
Bài tập này sẽ sớm mở.
Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.