Problem statement

https://binarysearch.com/problems/Sustainable-Consumption/

Solution

Use differences array and compression of index.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, P, C):
        x = []
        for s, e, _ in P + C:
            x += [s, e + 1]
        d = {x: i for i, x in enumerate(sorted(set(x)))}

        diff = [0]*(len(d) + 1)
        for s, e, w in P:
            diff[d[s]] += w
            diff[d[e + 1]] -= w

        for s, e, w in C:
            diff[d[s]] -= w
            diff[d[e + 1]] += w

        return min(accumulate(diff)) >= 0