Xử Lý Hàng Đợi Job AI VNetwork

Mô tả

Trung tâm Dữ Liệu VNetwork tiếp nhận các lô tác vụ (job) huấn luyện mô hình AI từ khách hàng. Hệ thống điều phối chia tài nguyên GPU thành tối đa k luồng chạy song song, mỗi luồng chỉ xử lý một tác vụ tại một thời điểm.

Khi một tác vụ đến lượt và có luồng rảnh, hệ thống lập tức cấp phát luồng đó. Tác vụ nào đến trước được xếp trước. Thời điểm một tác vụ hoàn thành bằng thời điểm nó bắt đầu chạy cộng với thời lượng xử lý. Bạn hãy tính thời điểm tác vụ cuối cùng hoàn thành — tức tổng thời gian cần thiết để dọn sạch toàn bộ lô.

Đầu vào

• Số nguyên n (1 ≤ n ≤ 10^5) — số lượng tác vụ trong lô.
• Số nguyên k (1 ≤ k ≤ 10^5) — số luồng chạy song song tối đa.
• Mảng times gồm n số nguyên dương — times[i] là thời lượng xử lý của tác vụ thứ i theo thứ tự đến.

Đầu ra

• Trả về một số nguyên dương — thời điểm tác vụ cuối cùng hoàn thành (tính từ thời điểm 0).

Ràng buộc

• 1 ≤ n ≤ 10^5
• 1 ≤ k ≤ 10^5
• 1 ≤ times[i] ≤ 10^6
• Tổng thời gian có thể lên tới khoảng 10^11, cần dùng kiểu số nguyên 64-bit trong ngôn ngữ biên dịch.

Ví dụ

Ví dụ 1:

• Đầu vào: n = 5, k = 2, times = [4, 3, 6, 2, 5]
• Đầu ra: 13

Giải thích từng bước:

• Thời điểm 0: tác vụ 0 (thời lượng 4) vào luồng A, tác vụ 1 (thời lượng 3) vào luồng B.
• Thời điểm 3: tác vụ 1 xong, tác vụ 2 (thời lượng 6) vào luồng B, dự kiến xong lúc 9.
• Thời điểm 4: tác vụ 0 xong, tác vụ 3 (thời lượng 2) vào luồng A, dự kiến xong lúc 6.
• Thời điểm 6: tác vụ 3 xong, tác vụ 4 (thời lượng 5) vào luồng A, dự kiến xong lúc 11.
• Thời điểm 9: tác vụ 2 xong, không còn tác vụ chờ.
• Thời điểm 11: tác vụ 4 xong cuối cùng.

Đáp án: 11.

Ví dụ 2:

• Đầu vào: n = 3, k = 5, times = [2, 7, 4]
• Đầu ra: 7

Giải thích: vì k lớn hơn số tác vụ, cả ba cùng chạy song song từ thời điểm 0. Tác vụ dài nhất là 7, nên thời điểm hoàn thành cuối cùng là 7.