대관료가 가장 큰 행사 편성

문제

행사장 하나를 운영하는 대관 담당자가 신청서를 심사합니다. 행사장은 한 번에 한 행사만 치를 수 있고, 담당자는 받는 대관료의 합 을 가장 크게 만들고 싶어 합니다.

bookings[i] = [start, end, teardown, fee]는 i번째 신청서를 뜻합니다.

• start, end: 행사가 시각 start에 시작해 시각 end에 끝납니다
• teardown: 행사가 끝난 뒤 무대를 걷어내는 데 걸리는 시간 — 행사마다 다릅니다
• fee: 이 행사를 승인했을 때 받는 대관료

어떤 행사를 승인하면 행사장은 end + teardown 시각까지 묶여 있습니다. 따라서 다음으로 승인하는 행사는 시작 시각이 end + teardown 이상 이어야 합니다 (같은 시각에 시작하는 것은 허용됩니다).

승인한 행사들의 대관료 합의 최댓값 을 반환하는 solution(bookings) 함수를 작성하세요.

예시

bookings=[[1,4,1,50],[2,6,0,90],[5,8,2,60]] → 110
  [1,4] 승인 → 철거까지 시각 5. [5,8]은 5부터 시작하므로 이어서 승인.
  50 + 60 = 110 이 [2,6] 한 건만 받는 90보다 큽니다.
 
bookings=[[0,10,0,100],[1,3,0,20],[4,6,0,30],[7,9,0,25]] → 100
  짧은 행사 세 건을 모두 받아도 20 + 30 + 25 = 75.
  긴 행사 한 건을 받는 100이 더 큽니다.
 
bookings=[[0,3,5,40],[3,6,0,50]] → 50
  첫 행사는 철거까지 시각 8이 걸려 [3,6]과 겹칩니다. 둘 중 비싼 한 건만 받습니다.

제약 조건

• 1 ≤ bookings.length ≤ 100,000
• 0 ≤ start < end ≤ 10^9
• 0 ≤ teardown ≤ 10^6
• 1 ≤ fee ≤ 10^6
• 시작·종료 시각이 완전히 같은 신청서가 여러 건 들어올 수 있습니다

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