1124. Longest Well-Performing Interval
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 <= 104
0 <= 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|