Problem statement

https://binarysearch.com/problems/Interval-Painting/

Solution

Use line sweep here with coordinate compression.

Complexity

Code

class Solution:
    def solve(self, W, target):
        P = [0] + list(accumulate(W))
        points = sorted(set(P))
        d = {x: i for i, x in enumerate(points)}

        diff = [0]*(len(d) + 1)
        for s, e in zip(P, P[1:]):
            x, y = min(d[s], d[e]), max(d[s], d[e])
            diff[x] += 1
            diff[y] -= 1

        acc = list(accumulate(diff))
        return sum(points[i+1] - points[i] for i in range(len(diff) - 1) if acc[i] >= target)