Problem statement

https://binarysearch.com/problems/Scrum-Journeyman/

Solution

The idea is to use line sweep with index compression here. Notice, that types do not matter at all here.

Complexity

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

Code

class Solution:
    def solve(self, I, types):
        P = sorted(set([x for x, _ in I] + [y for _, y in I]))
        d = {x:i for i, x in enumerate(P)}
        m = len(P)
        diff = [0] * (m + 1)
        for i in range(len(I)):
            x, y = d[I[i][0]], d[I[i][1]]
            diff[x] += 1
            diff[y] -= 1

        acc = list(accumulate(diff))
        ans = [[P[i], P[i+1], acc[i]] for i in range(m - 1) if acc[i]]
        return ans