콜센터 멀티 큐 라우팅

문제

한 콜센터에는 상담 유형이 0번부터 k-1번까지 k가지 있고, 유형마다 별도의 대기열(큐)이 하나씩 있습니다. 상담사는 N명이며, 상담사마다 처리할 수 있는 유형이 다릅니다.

고객 정보는 customers[j] = [arrival, type, duration]으로 주어집니다 — 도착 시각, 상담 유형, 상담에 걸리는 시간입니다. 시뮬레이션은 시각 0부터 1 단위씩 진행되며, 매 시각 t에 다음 순서로 처리합니다.

1. 접수: 시각 t에 도착한 고객을 주어진 입력 순서대로 처리합니다. 해당 유형을 처리할 수 있는 상담사가 한 명도 없으면 그 고객은 즉시 반려 되고(대기열에 들어가지 않음), 그렇지 않으면 자기 유형의 대기열 맨 뒤에 들어갑니다.
2. 배정: 시각 t에 한가한 상담사를 번호가 작은 순서대로 한 명씩 확인합니다. 각 상담사는 자신이 처리 가능한 유형의 대기열들 중 맨 앞 고객들만 비교하여, 도착 시각이 가장 이른 고객을 배정받습니다. 도착 시각이 같으면 유형 번호가 작은 쪽을 선택합니다. 처리 가능한 대기열이 모두 비어 있으면 그 시각에는 쉽니다.
   • 시각 s에 배정받은 상담사는 시각 s + duration부터 다시 한가해집니다. 즉 시각 s + duration에 새 고객을 배정받을 수 있습니다.
   • 도착한 시각에 바로 배정되면 대기 시간은 0입니다.
3. 관측: 접수와 배정이 모두 끝난 직후, 각 유형 대기열의 길이 중 최댓값을 기록합니다.

고객의 대기 시간 은 배정 시각 - 도착 시각입니다.

접수된 모든 고객이 배정될 때까지 시뮬레이션한 뒤, 다음 세 값을 배열로 반환하는 solution(k, agents, customers) 함수를 작성하세요.

• [0] 배정된 고객들의 대기 시간 총합
• [1] 시뮬레이션 전체에서 관측된 단일 대기열 길이의 최댓값 (관측된 적이 없으면 0)
• [2] 반려된 고객 수

agents[i]는 상담사 i가 처리할 수 있는 유형 번호의 배열입니다. customers는 도착 시각 오름차순으로 주어지며, 도착 시각이 같은 고객은 배열에 나온 순서대로 접수됩니다.

예시

예시 1 설명: 시각 0에 상담사 0이 유형 0 고객을, 상담사 1이 유형 1 고객을 받습니다(대기 0). 시각 2에 상담사 1이 한가해지고, 유형 0 대기열 맨 앞(도착 1)이 유형 1 맨 앞(도착 2)보다 이르므로 유형 0 고객을 받습니다(대기 1). 남은 유형 1 고객은 상담사 0이 처리할 수 없어, 상담사 1이 다시 한가해지는 시각 6에 배정됩니다(대기 4). 총합 0+0+1+4=5, 대기열 길이 최댓값 1, 반려 0.

예시 2 설명: 유형 2는 처리 가능한 상담사가 없어 첫 고객이 반려됩니다. 시각 0에 유형 0과 유형 1 맨 앞 고객의 도착 시각이 같아 유형 번호가 작은 유형 0이 먼저 배정되고, 유형 1 대기열에 2명이 남아 최댓값은 2입니다.

제약 조건

• 1 ≤ k ≤ 10
• 1 ≤ agents.length ≤ 20, 각 agents[i]는 0 이상 k-1 이하의 서로 다른 유형 번호로 구성 (1 ≤ agents[i].length ≤ k)
• 0 ≤ customers.length ≤ 2,000
• customers[j] = [arrival, type, duration], 0 ≤ arrival ≤ 10,000, 0 ≤ type ≤ k-1, 1 ≤ duration ≤ 50
• customers는 도착 시각 오름차순으로 정렬되어 주어짐

시간 복잡도 목표: O(T × N × k) — T는 시뮬레이션 총 시각 수