Problem statement

https://binarysearch.com/problems/Weighted-Merge-Interval/

Solution

Use trick where we keep differences and then use accumulate. Also use coordinate compression.

Complexity

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

Code

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

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

        acc = list(accumulate(diff))
        ans = []
        mx = max(acc)

        for i in range(len(acc)):
            if acc[i] == mx:
                if ans and ans[-1][-1] + 1 == i:
                    ans[-1][-1] = i
                else:
                    ans += [[i, i]]

        return [[points[i], points[j+1] - 1] for i, j in ans]