BinarySearch 0540 Most Frequent Number in Intervals

Problem statement

https://binarysearch.com/problems/Most-Frequent-Number-in-Intervals/

Solution

Use classical linesweep here with accumulate trick.

Complexity

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

Code

class Solution:
    def solve(self, I):
        vals = sorted(set(chain(*I)))
        d = {v: i for i, v in enumerate(vals)}

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

        acc = list(accumulate(P))
        return vals[acc.index(max(acc))]