Giả sử ta có danh sách hours, đây là danh sách số giờ làm việc mỗi ngày của một nhân viên. Một ngày được coi là mệt mỏi nếu và chỉ nếu số giờ làm việc lớn hơn 8 (chặt chẽ). Một khoảng thời gian hiệu quả là khoảng ngày mà số ngày mệt mỏi lớn hơn chặt chẽ số ngày không mệt mỏi. Ta phải tìm độ dài khoảng thời gian hiệu quả dài nhất. Nếu đầu vào như [9,9,6,0,6,6,9], kết quả là 3. Vì khoảng hiệu quả dài nhất là [9,9,6].
Để giải quyết, ta làm theo các bước −
- gán temp := 0 và ans := 0, tạo map d, corner := 0
- với i từ 0 đến len(hours)-1
- temp := temp + 1 nếu hours[i] > 8, ngược lại -1
- nếu hours[i] > 8, corner = 1
- nếu temp > 0, ans := max(ans, i + 1)
- nếu temp không trong map d, d[temp] := i
- nếu temp - 1 trong map d, ans := max(ans, i - d[temp - 1])
Xem triển khai sau để hiểu rõ hơn −
Ví dụ
class Solution(object): def longestWPI(self, hours): temp = 0 ans = 0 d = {} corner = 0 for i in range(len(hours)): temp += 1 if hours[i]>8 else -1 if hours[i]>8: corner = 1 if temp>0: ans = max(ans,i+1) if temp not in d: d[temp]=i if temp-1 in d: ans = max(ans,i-d[temp-1]) return max(ans,0) ob = Solution() print(ob.longestWPI([9,9,6,0,6,6,9]))Đầu vào
[9,9,6,0,6,6,9]
Kết quả
3