Longest Well-Performing Interval LeetCode solution in Python

1
class Solution:
2
    def longestWPI(self, hours: List[int]) -> int:
3
        # accumulative count
4
        # +1 when > 8, -1 when less than 8.
5
        # find strictly increasing length.
6

7
        p = []  # number of tiring days vs not
8
        c = 0
9
        for e in hours:
10
            if e > 8:
11
                c += 1
12
            else:
13
                c -= 1
14

15
            p.append(c)
16

17
        # for every moment: we want earliest moment which could be positive overall tiring days.
18
        a = []
19
        # a is sorted by tiringnes. At day 8 have -2, want earliest point that could get us to at least 1.
20
        # so up until that point we have -3, -4, etc, and we want earliest out of it to get longest well performing interval. Which is when prefix comes in.
21

22
        a1 = []
23
        for i in range(len(p)):
24
            a.append([p[i], i])
25
            a1.append(p[i])
26

27
        a1.sort()  # bisectable list
28
        a.sort()
29

30
        prefix = []
31
        currearly = float("inf")
32
        for t, day in a:
33
            currearly = min(currearly, day)
34
            prefix.append(currearly)
35

36
        res = 0
37

38
        # print(p)
39

40
        for i in range(len(hours)):
41
            if p[i] > 0:
42
                res = max(res, i + 1)
43

44
            else:
45
                # find earliest
46
                # value must be less than -1-p[i]
47
                loc = bisect_right(
48
                    a1, -1 + p[i]
49
                )  # bisect right means anything before this is less than or equals to
50

51
                if loc == 0:  # the rightmost place to put it is at the beginning...
52

53
                    continue
54

55
                else:
56
                    earliest = prefix[loc - 1]
57

58
                    if earliest >= i:
59
                        continue
60

61
                    interval = (
62
                        i - earliest
63
                    )  # notice: we're not including the starting index, since its also technically being removed!
64

65
                    # print("From day", earliest, "to", i)
66

67
                    res = max(res, interval)
68

69
        return res