Mượn phân loại cấp cứu: sắp thứ tự một hàng đợi tác vụ
Vì sao điều này quan trọng "Dùng một hàng đợi ưu tiên" là phản xạ cho bất kỳ hàng đợi nào có mức ưu tiên. Nó trả lời "ai quan trọng nhất?" trong khi câu hỏi thật thường là "ai ít chờ được nhất?". Các lĩnh vực khác đã trả lời câu hỏi đó từ lâu.
Ba quầy
Một khoa cấp cứu bệnh viện. Một y tá phân loại xếp mỗi người tới vào một hạng mục, và mỗi hạng mục có một thời gian mục tiêu để được khám: trong hệ thống Manchester được dùng rộng rãi, ngay lập tức, trong vòng 10 phút, 60, 120 hay 240. Khi một bác sĩ rảnh, bệnh nhân tiếp theo không đơn giản là người ốm nhất trong phòng: một bệnh nhân thông thường sắp quá thời gian mục tiêu có thể vào trước một ca khẩn mới tới một phút trước và vẫn còn thời gian.
Quầy làm thủ tục ở sân bay. Có các làn riêng cho hạng cao cấp và hạng phổ thông. Trong một làn, mọi người được phục vụ theo thứ tự đến. Nhưng khi một chuyến bay sắp đóng quầy, nhân viên đi dọc hàng phổ thông gọi chuyến bay đó lên trước, vượt trước những hành khách cao cấp có chuyến bay khởi hành muộn hơn.
Một quầy trả sách ở thư viện. Một hàng, phục vụ nghiêm ngặt theo thứ tự. Không ai từng bị vượt, và sự khẩn cấp của không ai được xét tới.
So sánh trước khi viết mã
- Ở mỗi quầy, điều gì quyết định ai được phục vụ tiếp theo?
- Quầy nào có thể khiến ai đó chờ mãi mãi? Quầy nào có thể khiến một ca khẩn chờ quá lâu?
- Bệnh viện và sân bay trông chẳng giống nhau chút nào. Chúng có chung điều gì? Hãy viết nó thành một câu không nhắc tới bệnh viện hay máy bay.
- Ở sân bay, vì sao chỉ cần nhìn vào đầu mỗi làn là đủ?
Bài toán đích
Một hệ thống tác vụ nền chạy trên một máy làm việc mất đúng một phút cho mỗi tác vụ. Các tác vụ là tương tác (ưu tiên 1), tiêu chuẩn (2) hoặc theo lô (3), và mỗi mức ưu tiên có một cam kết dịch vụ: thời gian lâu nhất mà một tác vụ ở mức ưu tiên đó có thể chờ trước khi bắt đầu. Bộ lập lịch hiện tại luôn chạy tác vụ đang chờ có ưu tiên cao nhất, và các tác vụ theo lô trễ cam kết mỗi buổi chiều.
Viết order(jobs, max_wait). jobs là một list các {"id", "arrive", "priority"} sắp xếp theo arrive (phút nguyên); max_wait ánh xạ mức ưu tiên tới số phút tối đa mà một tác vụ có thể chờ. Trả về các id tác vụ theo thứ tự máy làm việc chạy chúng. Máy làm việc chạy một tác vụ mỗi phút: một tác vụ bắt đầu ở thời điểm muộn hơn giữa lúc nó đến và lúc tác vụ trước kết thúc, và thời gian chờ của nó là lúc bắt đầu trừ lúc đến. Quy tắc: không tác vụ nào được chờ lâu hơn max_wait[priority]. Mọi ngày kiểm thử đều có thể được phục vụ mà không tác vụ nào trễ; với {1: 3, 2: 20, 3: 60} một ngày có khoảng 1.000 tác vụ.
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.