Mượn hàng đợi giữ chỗ: đặt trước công bằng
Vì sao điều này quan trọng Các hệ thống đặt trước dựng từ đầu có xu hướng thưởng cho ai nhấp nhanh nhất, hoặc để một người không tới chặn tất cả những người khác. Những nơi phát những thứ khan hiếm cho người ta mỗi ngày đã chọn một thiết kế tốt hơn từ lâu.
Ba quầy
Giữ sách ở thư viện. Bạn đặt giữ một cuốn sách đang được mượn. Khi một bản được trả lại, nó đến với người đầu tiên trong hàng đợi giữ chỗ, người đó nhận một tin nhắn và vài ngày để tới lấy. Nếu họ không tới, bản sách đến với người tiếp theo, và người đầu tiên mất chỗ của mình.
Danh sách chờ ở nhà hàng với máy rung báo. Bạn để lại tên và nhận một máy rung báo. Khi một bàn trống, nhóm tiếp theo được báo và có năm phút để tới quầy tiếp tân, nếu không bàn đến với nhóm tiếp theo.
Số thứ tự ở quầy thịt nguội. Bạn lấy một số. Khi số của bạn được gọi và bạn không có mặt, số tiếp theo được gọi. Bạn có thể lấy một số mới, ở cuối hàng.
So sánh trước khi viết mã
- Ở mỗi nơi, khi nào chỗ của bạn trong hàng được cố định: khi bạn yêu cầu, hay khi thứ đó trở nên trống?
- Điều gì xảy ra với một người không tới, và họ có bao lâu?
- Điều gì xảy ra với thứ đó trong khi nó chờ ai đó tới lấy?
- Phát biểu quy tắc chung trong một câu không nhắc tới sách, bàn hay thịt.
Bài toán đích
Nhóm di động dùng chung một phòng thử nghiệm nhỏ gồm các điện thoại thử. Kỹ sư yêu cầu một mẫu máy; khi một điện thoại thuộc mẫu đó trống, nó được đề nghị cho họ, và họ phải nhận nó trong ứng dụng của phòng thử nghiệm trong vòng hai giờ. Một điện thoại đã nhận được đặt cho một khung tám giờ rồi tự động quay về. Hiện nay ứng dụng đưa một điện thoại trống cho ai bấm "nhận" đầu tiên, và người ta đã bắt đầu viết script để bấm nó.
stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events) # -> [("ana", "dev1", 30)] (ben is not first)Viết loans(stock, events). stock liệt kê các (device_id, model), tất cả đều trống ở thời điểm 0. events là ("request", t, person, model) hoặc ("claim", t, person, model), sắp xếp theo thời gian t tính bằng phút. Các quy tắc:
- Mỗi mẫu máy có một hàng đợi theo thứ tự yêu cầu. Một yêu cầu bị bỏ qua nếu người đó đã ở trong hàng đợi, hoặc đang giữ một lời đề nghị, cho mẫu đó.
- Một điện thoại trống được đề nghị cho người đầu tiên trong hàng đợi của mẫu đó (họ rời hàng đợi). Nếu không ai trong hàng đợi, nó chờ trên kệ, và một yêu cầu sau đó cho mẫu đó nhận nó ngay. Với vài cái trên kệ, đề nghị device id nhỏ nhất.
- Một lời đề nghị được đưa ra ở thời điểm
ocó thể được nhận khit < o + 120. Một lần nhận mà không có lời đề nghị còn hiệu lực cho người và mẫu đó bị bỏ qua. - Ở
o + 120một lời đề nghị chưa được nhận hết hiệu lực và điện thoại lại trống ngay lúc đó (quy tắc 2). - Một lần nhận ở thời điểm
tbắt đầu một lượt mượn; điện thoại trống lại ởt + 480. - Các lần hết hiệu lực và trả máy tới hạn vào hoặc trước thời điểm của một sự kiện xảy ra trước nó, theo thứ tự thời gian, rồi theo device id.
(person, device_id, claim_time) theo thứ tự chúng được nhậ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.