Algorithm
Problem Name: 1124. Longest Well-Performing Interval
Problem Link: https://leetcode.com/problems/longest-well-performing-interval/
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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int longestWPI(int[] hours) {
int sum = 0;
int maxInterval = 0;
boolean greaterThanEightFound = false;
Map < Integer, Integer> map = new HashMap<>();
for (int i = 0; i < hours.length; i++) {
sum += hours[i] > 8 ? 1 : -1;
greaterThanEightFound = hours[i] > 8 ? true : greaterThanEightFound;
map.putIfAbsent(sum, i);
if (sum >= 1) {
maxInterval = Math.max(maxInterval, i + 1);
}
else if (map.containsKey(sum - 1)) {
maxInterval = Math.max(maxInterval, i - map.get(sum - 1));
}
}
return maxInterval == 0 ? (greaterThanEightFound ? 1 : 0) : maxInterval;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const longestWPI = function(hours) {
const N = hours.length;
const seen = new Map();
let res = 0;
let score = 0;
for (let i = 0; i < N; i++) {
score += hours[i] > 8 ? 1 : -1;
if (score > 0) {
res = i + 1;
} else {
if (!seen.has(score)) {
seen.set(score, i);
}
if (seen.has(score - 1)) {
res = Math.max(res, i - seen.get(score - 1));
}
}
}
return res;
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestWPI(self, hours: List[int]) -> int:
res = score = 0
seen = {}
for i, h in enumerate(hours):
score += h > 8
score -= h < 9
if score > 0:
res = i + 1
seen.setdefault(score, i)
if score - 1 in seen:
res = max(res, i - seen[score - 1])
return res
Input