스터디룸 예약 승인

문제

도서관 스터디룸 한 곳에 하루치 예약 신청이 밀려 있습니다. 신청 목록 requests 의 각 원소는 [시작, 종료] 이며, 개관 시각으로부터 몇 분 뒤인지를 나타냅니다.

스터디룸은 한 팀이 쓰고 나가면 정리·환기 시간 gap 분이 필요합니다. 즉 어떤 예약을 종료 분에 끝냈다면, 다음 예약은 종료 + gap 분 이후(같은 시각 포함)에 시작해야 승인할 수 있습니다.

관리자는 승인하는 예약의 개수를 최대로 만들고 싶습니다. 승인할 수 있는 예약의 최대 개수를 반환하세요. (예약 시간의 길이는 고려하지 않습니다.)

solution(requests: number[][], gap: number): number

예시

첫 번째 예시에서 승인되는 조합 중 하나는 [0,60], [75,135], [150,210] 입니다. [0,60] 이 끝난 뒤 정리 시간 10분이 필요하므로 다음 예약은 70분 이후에 시작해야 하고, 같은 이유로 [130,180] 은 [75,135] 뒤에 이어서 쓸 수 없습니다.

네 번째 예시는 정리 시간이 30분이나 되어, 붙어 있는 세 예약 중 두 개까지만 승인됩니다.

제약 조건

• 1 ≤ requests.length ≤ 200,000
• 0 ≤ 시작 < 종료 ≤ 1,000,000
• 0 ≤ gap ≤ 1,000
• 같은 시간대에 겹치는 신청이 여러 개 들어올 수 있습니다

시간 복잡도 목표: O(N log N)