Khung Giờ Cao Điểm Dầu Giây

Mô tả

Trạm thu phí Dầu Giây những ngày lễ luôn trong tình trạng quá tải. Để điều phối giao thông, đội quản lý đã chia ngày thành các khung giờ liên tiếp, mỗi khung giờ kéo dài đúng 1 tiếng. Hệ thống camera đếm số lượng xe chạy qua trạm trong từng khung giờ và lưu lại thành một mảng.

Nhiệm vụ của bạn là tìm ra một khoảng khung giờ liên tiếp sao cho tổng số xe ghi nhận trong khoảng đó bằng đúng $k$. Vì trạm cần phản ứng nhanh nhất có thể, bạn phải ưu tiên khoảng ngắn nhất (ít khung giờ nhất). Nếu có nhiều khoảng cùng độ dài ngắn nhất, hãy lấy khoảng xuất hiện đầu tiên. Trả về chỉ số của khung giờ bắt đầu và khung giờ kết thúc (đánh chỉ số từ 0). Trong trường hợp không tồn tại khoảng nào thỏa mãn, hãy trả về cặp $[-1, -1]$.

Đầu vào

• Mảng traffic: danh sách số lượng xe của từng khung giờ.
• Số nguyên $k$: tổng số xe mục tiêu của khoảng cần tìm.

Đầu ra

• Một mảng gồm hai số nguyên $[start, end]$, lần lượt là chỉ số bắt đầu và kết thúc của khoảng khung giờ ngắn nhất có tổng đúng $k$. Nếu không tìm thấy, trả về $[-1, -1]$.

Ràng buộc

• $1 \le n \le 10^5$ (với $n$ là độ dài mảng traffic).
• $1 \le \text{traffic}[i] \le 10^6$.

Ví dụ

Ví dụ 1:

• Đầu vào: traffic = [2, 3, 1, 2, 4, 3], k = 7
• Đầu ra: [3, 5]
• Giải thích: Khoảng từ chỉ số 3 đến 5 (các giá trị 2, 4, 3) có tổng là $2 + 4 + 3 = 9$. Đây là khoảng ngắn nhất đạt mức $\ge k$. (Lưu ý, cần tìm khoảng có tổng đúng bằng $k$, ta xem các ví dụ tiếp theo để làm rõ quy trình).

Ví dụ 2:

• Đầu vào: traffic = [2, 3, 1, 2, 4, 3], k = 8
• Đầu ra: [1, 4]
• Giải thích: Ta tìm khoảng có tổng đúng bằng 8:
  • [2, 3, 1, 2] có tổng $8$, độ dài $4$.
  • [4, 3] có tổng $7$ (loại). Đoạn [2, 3, 1, 2] (từ chỉ số 0 đến 3) là một đáp án. Tuy nhiên nếu ta lấy chỉ số từ [1, 4] (các giá trị 3, 1, 2, 4) thì tổng cũng là $3 + 1 + 2 + 4 = 10$. Để tránh nhầm lẫn, với , đoạn ngắn nhất cho tổng bằng 8 chính là với kết quả .

Ví dụ 3 (minh họa rõ ràng nhất):

• Đầu vào: traffic = [1, 2, 3, 4, 5], k = 9
• Đầu ra: [1, 3]
• Giải thích:
  • Khoảng [0, 3] có tổng $1 + 2 + 3 + 4 = 10$.
  • Khoảng [1, 3] có tổng $2 + 3 + 4 = 9$ (đúng bằng , độ dài 3).