1. Câu hỏi

Cung cấp cho bạn một tác vụ mảng hai chiều, dùng để biểu diễn n tác vụ được đánh số từ 0 đến n - 1. TRONG task[i] = [enqueueTimei,processTimei] có nghĩa là task thứ i sẽ vào hàng đợi task tại enqueueTimei và yêu cầuprocessTimei để hoàn thành việc thực thi.

Có một CPU đơn luồng,Chỉ có thể thực hiện một nhiệm vụ cùng một lúc, CPU sẽ hoạt động như sau:

Nếu CPU không hoạt động và không có tác vụ nào trong hàng tác vụ cần được thực thi thì CPU vẫn ở chế độ rảnh.
Nếu CPU không hoạt động nhưng có các tác vụ trong hàng đợi tác vụ cần được thực thi thì CPU sẽChọn tác vụ có thời gian thực hiện ngắn nhất để bắt đầu thực hiện. Nếu nhiều tác vụ có cùng thời gian thực hiện tối thiểu thì tác vụ có chỉ mục nhỏ nhất sẽ được chọn để bắt đầu thực thi.
Khi một tác vụ bắt đầu thực thi, CPU sẽ không dừng cho đến khi toàn bộ tác vụ được thực thi.
CPU có thể ngay lập tức bắt đầu một nhiệm vụ mới sau khi hoàn thành một nhiệm vụ.
Trả về thứ tự CPU xử lý các tác vụ.

Ví dụ 1:

Đầu vào: task = [[1,2],[2,4],[3,2],[4,1]] Đầu ra: [0,2,3,1] Giải thích: Sự kiện diễn ra theo quy trình sau : - thời gian = 1, tác vụ 0 vào hàng tác vụ, mục tác vụ thực thi = {0} - cũng tại thời điểm = 1, CPU ở trạng thái rảnh bắt đầu thực thi tác vụ 0, mục tác vụ thực thi = {} - time = 2, tác vụ 1 Nhập hàng tác vụ, mục tác vụ thực thi = {1} - time = 3, tác vụ 2 vào hàng tác vụ, mục tác vụ thực thi = {1, 2} - cũng tại thời điểm = 3, CPU hoàn thành tác vụ 0 và bắt đầu thực thi thời gian trong hàng đợi Nhiệm vụ ngắn nhất 2, mục nhiệm vụ thực thi = {1} - time = 4, nhiệm vụ 3 vào hàng đợi nhiệm vụ, mục nhiệm vụ thực thi = {1, 3} - time = 5, CPU hoàn thành nhiệm vụ 2 Và bắt đầu thực thi tác vụ 3 ngắn nhất trong hàng đợi, tác vụ thực thi được item = {1} - time = 6, CPU hoàn thành tác vụ 3 và bắt đầu thực thi tác vụ 1, tác vụ thực thi được item = {} - time = 10, CPU hoàn thành tác vụ 1 và nhập trạng thái nhàn rỗi

Ví dụ 2:

Đầu vào: task = [[7,10],[7,12],[7,5],[7,4],[7,2]] Đầu ra: [4,3,2,0,1] Giải thích: Sự kiện diễn ra theo quy trình sau: - thời gian = 7, tất cả các tác vụ vào hàng đợi tác vụ cùng lúc, các mục tác vụ thực thi = {0,1,2,3,4} - Cũng tại thời điểm = 7, CPU nhàn rỗi bắt đầu thực hiện nhiệm vụ 4 , mục tác vụ thực thi = {0,1,2,3} - time = 9, CPU hoàn thành nhiệm vụ 4 và bắt đầu thực thi nhiệm vụ 3, mục tác vụ thực thi = {0,1,2} - time = 13, CPU hoàn thành nhiệm vụ 3 và bắt đầu thực thi tác vụ 2, mục tác vụ thực thi = {0,1} - time = 18, CPU hoàn thành tác vụ 2 và bắt đầu thực thi tác vụ 0, mục tác vụ thực thi = {1} - time = 28 , CPU hoàn thành nhiệm vụ 0 và bắt đầu thực thi nhiệm vụ 1, nhiệm vụ thực thi item = {} - time = 40, CPU hoàn thành nhiệm vụ 1 và chuyển sang trạng thái rảnh

gợi ý:
nhiệm vụ.length == n
1 <= n <= 105
1 <= enqueueTimei, thời gian xử lý <= 109

Nguồn: LeetCode
Liên kết: https://leetcode.cn/problems/single-threaded-cpu

2. Ý tưởng

(1) Vấn đề về khoảng thời gian

3. Triển khai mã (Java)

//Ý tưởng 1——Vấn đề khoảng thời gian public int[] getOrder(int[][] task) { //Có tổng cộng n nhiệm vụ int n = task.length; ArrayList triples = new ArrayList<> ( ); for (int i = 0; i < n; i++) { triples.add(new int[]{tasks[i][0], task[i][1], i} } // Sắp xếp các tác vụ theo thứ tự tăng dần theo thời gian bắt đầu triples.sort((a, b) -> { //Nếu giá trị trả về là số dương, đổi chỗ a và b return a[0] - b[0]; } ); // Sắp xếp tăng dần theo thời gian thực hiện của task. Nếu thời gian thực hiện giống nhau thì sắp xếp tăng dần theo chỉ số PriorityQueue pqueue = new PriorityQueue<>((a). , b) -> { if (a[ 1] != b[1]) { //So sánh thời gian thực hiện return a[1] - b[1] } else { //So sánh các chỉ số dưới return a[2] - b[2] } }); new ArrayList<>(); //Ghi lại tiến trình hoàn thành nhiệm vụ int time = 0; int i = 0; while (res.size() < n) { if (!pqueue.isEmpty()) { //Hoàn thành một nhiệm vụ trong hàng đợi int[] triple = pqueue.poll(); )[0] > dòng thời gian) { //Hàng đợi có thể trống vì chưa đến thời gian bắt đầu, do đó dòng thời gian có thể được nâng thẳng lên thời gian bắt đầu của dòng thời gian nhiệm vụ mới nhất = triples.get(i)[0 ]; // Khi dòng thời gian trôi qua, các tác vụ có thể bắt đầu sẽ được tạo trong khi (i < n && triples.get(i)[0] <= dòng thời gian) { pqueue.offer(triples.get(i)); } //Chuyển đổi danh sách thành int[] return res.stream().mapToInt(Integer::valueOf).toArray() }