Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go

• class Solution {
      public int longestWPI(int[] hours) {
          int ans = 0, s = 0;
          Map<Integer, Integer> pos = new HashMap<>();
          for (int i = 0; i < hours.length; ++i) {
              s += hours[i] > 8 ? 1 : -1;
              if (s > 0) {
                  ans = i + 1;
              } else if (pos.containsKey(s - 1)) {
                  ans = Math.max(ans, i - pos.get(s - 1));
              }
              pos.putIfAbsent(s, i);
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int longestWPI(vector<int>& hours) {
          int ans = 0, s = 0;
          unordered_map<int, int> pos;
          for (int i = 0; i < hours.size(); ++i) {
              s += hours[i] > 8 ? 1 : -1;
              if (s > 0) {
                  ans = i + 1;
              } else if (pos.count(s - 1)) {
                  ans = max(ans, i - pos[s - 1]);
              }
              if (!pos.count(s)) {
                  pos[s] = i;
              }
          }
          return ans;
      }
  };
  

• 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
  
  

• func longestWPI(hours []int) (ans int) {
  	s := 0
  	pos := map[int]int{}
  	for i, x := range hours {
  		if x > 8 {
  			s++
  		} else {
  			s--
  		}
  		if s > 0 {
  			ans = i + 1
  		} else if j, ok := pos[s-1]; ok {
  			ans = max(ans, i-j)
  		}
  		if _, ok := pos[s]; !ok {
  			pos[s] = i
  		}
  	}
  	return
  }
  

All Problems

All Solutions