Chương trình học Bài 3 trên tổng số 148 · Khởi đầu mù
Khởi đầu mù

Bài đầu vào 2: một giờ hợp với mọi người

Tắt AI Đây là một bài kiểm tra đầu vào. Người hướng dẫn bị tắt và không có gợi ý nào. Hãy tự làm, theo cách bạn sẽ làm khi không mở trợ lý nào. Không có gì ở đây là mẹo: mọi quy tắc đều được viết trong bài tập. Kết quả của bạn chỉ được so sánh với bài thi cuối của chính bạn ở cuối khóa học.

Hãy dành cho nó khoảng thời gian được ghi. Không qua là một kết quả ổn với một bài đầu vào: sau một lần Kiểm tra, Lưu lại lần thử này và tiếp tục mở bài học tiếp theo, và bài đầu vào không cần thiết cho chứng chỉ.

Một dịch vụ xếp lịch tìm thời điểm sớm nhất cả một nhóm có thể họp. Lịch của mỗi người nằm trong một kho riêng, và mỗi mục được lấy về tốn một lần gọi mạng, nên dịch vụ bị tính tiền theo số mục đã đọc. Các nhóm thì lớn và lịch kéo dài nhiều năm về trước.

Một ví dụ nhỏ

from creative.budget import Tape
cals = [[(0, 30), (60, 90)], [(10, 40)], []]
earliest_slot([Tape(c) for c in cals], 0, 15)   # -> 40  (free from 40 to 60)
earliest_slot([Tape(c) for c in cals], 0, 20)   # -> 40  (40 + 20 = 60: touching is fine)
earliest_slot([Tape(c) for c in cals], 0, 25)   # -> 90
Đến lượt bạn

Viết earliest_slot(calendars, after, length). calendars là một list các Tape, mỗi người một cái. Mỗi cái giữ các cuộc họp của người đó dưới dạng các cặp phút (start, end), sắp xếp theo start; một cuộc họp bận từ start tới trước end (không gồm), và các cuộc họp của một người không bao giờ chồng lên nhau (chúng có thể chạm nhau). Trả về phút sớm nhất t >= after sao cho không ai bận ở bất kỳ đâu trong [t, t + length). Mọi người đều rảnh sau cuộc họp cuối cùng của mình, nên luôn có một đáp án.
Ngân sách: có 50 người, mỗi người 2.000 cuộc họp (100.000 mục), và after thường đã vào sâu nhiều tháng trong dữ liệu. Một lần tìm kiế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 (truy cập theo chỉ số, cắt lát và lặp đều dùng được), 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ờ.