Problem statement

https://binarysearch.com/problems/DDoS-Protection/

Solution

We need to keep queue for all persons as we as individual queue for each pereson. We chech that we keep only last 60 seconds in our queue.

Complexity

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

Code

class Solution:
    def solve(self, R, u, g):
        R = sorted(R, key = lambda x: (x[1], x[0]))
        gl = deque()
        lc = defaultdict(deque)
        ans = 0
        for idx, time in R:
            while gl and gl[0] + 60 <= time: gl.popleft()
            while lc[idx] and lc[idx][0] + 60 <= time: lc[idx].popleft()
            if len(gl) < g and len(lc[idx]) < u:
                ans += 1
                gl += [time]
                lc[idx] += [time]

        return ans