축제 셔틀버스 혼잡 구간

문제

지역 축제 기간 동안 셔틀버스 한 대가 정류장 1번부터 n번까지 한 방향으로만 운행한다. 정류장 i와 i+1 사이의 길을 구간 i 라고 부른다 (구간은 총 n-1개).

예매 시스템에는 탑승 예약이 trips 배열로 기록되어 있다. trips[k] = [on, off, people]은 people명이 정류장 on에서 타서 정류장 off에서 내린다는 뜻이다. 이 승객들은 구간 on, on+1, ..., off-1을 지나는 동안 버스에 타고 있다. (정류장 off에서 내리는 승객은 구간 off에는 타고 있지 않다.)

버스의 정원은 capacity명이다. 어떤 구간의 탑승 인원이 capacity를 초과 하면 그 구간은 "정원 초과 구간"이다 (정확히 capacity명이면 초과가 아니다).

solution(n, capacity, trips)을 구현하여 다음 세 값을 배열로 반환하라.

1. maxLoad — 모든 구간 중 최대 탑승 인원 (예약이 없으면 0)
2. maxStart — 탑승 인원이 maxLoad인 구간 중 가장 번호가 작은 구간 번호
3. overCount — 정원 초과 구간의 개수

예시

첫 번째 예시: 구간별 탑승 인원은 구간 1부터 차례로 4, 10, 13, 6이다. 최대는 구간 3의 13명이고, 정원(10명)을 초과한 구간은 구간 3 하나뿐이다 (구간 2는 정확히 10명이라 초과가 아니다).

제약 조건

• 2 ≤ n ≤ 1,000,000,000
• 1 ≤ capacity ≤ 1,000,000,000
• 0 ≤ trips.length ≤ 100,000
• 각 예약 [on, off, people]은 1 ≤ on < off ≤ n, 1 ≤ people ≤ 10,000
• overCount는 매우 커질 수 있다 (n-1까지 가능) — 개수 자체를 정확히 반환해야 한다.

시간 복잡도 목표: O(m log m) (m = trips.length, n에 비례한 반복 금지)