각 목록에 [uid, time_sec]와 같은 요소가 포함된 요청 목록이 있다고 가정합니다(uid는 사용자 ID이고 time_sec는 타임스탬프입니다). 이것은 id가 uid인 사용자가 timestamp time_sec에 웹사이트에 요청했음을 나타냅니다. 우리는 또한 두 개의 값 u와 g가 있습니다. 여기서 u는 주어진 uid에 대해 60초 미만 프레임에서 허용되는 최대 요청 수를 나타내고 g는 전역적으로 60초 미만 프레임에서 허용되는 최대 요청 수를 나타냅니다. 이제 각 요청을 하나씩 처리하고 속도를 제한하려는 경우입니다. 그리고 여러 사용자가 동시에 요청하는 경우 uid가 낮은 요청이 먼저 처리되고 그렇지 않으면 해당 요청이 삭제됩니다. 성공적으로 처리될 총 요청 수를 찾아야 합니다.
따라서 입력이 requests =[[0, 1],[1, 2],[1,3]] u =1 g =5와 같으면 사용자 0과 1이 다음에서 보낼 수 있으므로 출력은 2가 됩니다. 1번과 2번 시간이지만 사용자 1의 두 번째 요청은 한 사용자가 60초 프레임에 최대 1개의 요청을 보낼 수 있으므로 처리되지 않습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 마지막 :=빈 지도
- 전체:=비어 있는 이중 종료 대기열
- 창 시간:=60
- 시간을 기준으로 요청을 정렬하고 동일한 경우 uid를 기준으로 정렬
- 금액:=0
- 요청의 각 r에 대해 다음을 수행합니다.
- [uid, 시간] :=r
- total size> 0 and total[0] + windowtime <=time, do
- 전체의 왼쪽 항목 삭제
- last[uid]의 크기> 0 및 last[uid, 0] + windowtime <=time, do
- 마지막[uid]에서 왼쪽 항목 삭제
- 총계의 크기가
- 마지막[uid] 끝에 시간 삽입
- 총계 끝에 시간 삽입
- 금액 :=금액 + 1
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
from collections import defaultdict, deque class Solution: def solve(self, requests, u, g): last = defaultdict(deque) total = deque() windowtime = 60 requests.sort(key=lambda x: [x[1], x[0]]) amount = 0 for r in requests: uid, time = r while len(total) > 0 and total[0] + windowtime <= time: total.popleft() while len(last[uid]) > 0 and last[uid][0] + windowtime <= time: last[uid].popleft() if len(total) < g and len(last[uid]) < u: last[uid].append(time) total.append(time) amount += 1 return amount ob = Solution() requests = [[0, 1],[1, 2],[1,3]] u = 1 g = 5 print(ob.solve(requests, u, g))
입력
[[0, 1],[1, 2],[1,3]], 1, 5
출력
2