Description
We are given hours, a list of the number of hours worked per day for a given employee.
A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.
A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.
Return the length of the longest well-performing interval.
Example 1:
Input: hours = [9,9,6,0,6,6,9] Output: 3 Explanation: The longest well-performing interval is [9,9,6].
Example 2:
Input: hours = [6,6,6] Output: 0
Constraints:
1 <= hours.length <= 1040 <= hours[i] <= 16
Solutions
Solution 1: Prefix Sum + Hash Table
We can use the idea of prefix sum, maintaining a variable s, which represents the difference between the number of "tiring days" and "non-tiring days" from index 0 to the current index. If s is greater than 0, it means that the segment from index 0 to the current index is a "well-performing time period". In addition, we use a hash table pos to record the first occurrence index of each s.
Next, we traverse the hours array, for each index i:
- If hours[i] > 8, we increment s by 1, otherwise we decrement s by 1.
- If s > 0, it means that the segment from index 0 to the current index i is a "well-performing time period", we update the result ans = i + 1. Otherwise, if s - 1 is in the hash table pos, let j = pos[s - 1], it means that the segment from index j + 1 to the current index i is a "well-performing time period", we update the result ans = max(ans, i - j).
- Then, if s is not in the hash table pos, we record pos[s] = i.
After the traversal, return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the hours array.
class Solution: def longestWPI(self, hours: List[int]) -> int: ans = s = 0 pos = {} for i, x in enumerate(hours): s += 1 if x > 8 else -1 if s > 0: ans = i + 1 elif s - 1 in pos: ans = max(ans, i - pos[s - 1]) if s not in pos: pos[s] = i return ans(code-box)
