Chương trình học Bài 50 trên tổng số 148 · Những cỗ máy đi mượn
Những cỗ máy đi mượn

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ã

  1. Ở 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?
  2. Điều gì xảy ra với một người không tới, và họ có bao lâu?
  3. Điều gì xảy ra với thứ đó trong khi nó chờ ai đó tới lấy?
  4. 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)
Đến lượt bạn

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:

  1. 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 đó.
  2. 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.
  3. Một lời đề nghị được đưa ra ở thời điểm o có thể được nhận khi t < 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.
  4. Ở o + 120 mộ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).
  5. Một lần nhận ở thời điểm t bắt đầu một lượt mượn; điện thoại trống lại ở t + 480.
  6. 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.
Trả về các lượt mượn dưới dạng (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ờ.