Skip to content

Longest Well-Performing Interval⚓︎

Link

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 <= 10^4
  • 0 <= hours[i] <= 16

Solution⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        unordered_map<int, int> prefixMap;
        prefixMap[0] = -1;
        int res = 0;

        for (int i = 0, sum = 0; i < hours.size(); i++) {
            sum += hours[i] > 8 ? 1 : -1;
            if (sum > 0) {
                res = i + 1;
            } else {
                if (prefixMap.find(sum - 1) != prefixMap.end()) {
                    res = max(res, i - prefixMap[sum - 1]);
                }
            }

            if (prefixMap.find(sum) == prefixMap.end()) {
                prefixMap[sum] = i;
            }
        }

        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).