두 가지 최고의 비중복 이벤트

2054. 겹치지 않는 두 가지 최고의 이벤트

난이도:중

주제: 배열, 이진 검색, 동적 프로그래밍, 정렬, 힙(우선순위 대기열)

이벤트의 0 인덱스 2D 정수 배열이 제공됩니다. 여기서 events[i] = [startTime_i, endTime_i, value _나]. i^번째 이벤트는 startTime_i에 시작하여 endTime_i에 종료되며, 이번 이벤트에 참여하시면 가치있는 보상을 받으실 수 있습니다_i . 최대 2개의 중복되지 않는 이벤트를 선택하여 해당 가치의 합이 최대화

되도록 참석할 수 있습니다.

이 최대 합계

를 반환합니다.

시작 시간과 종료 시간은 포함입니다. 즉, 한 이벤트가 시작되고 다른 이벤트가 동시에 끝나는 두 이벤트에 참석할 수 없습니다. 보다 구체적으로, 종료 시간이 t인 이벤트에 참석하는 경우 다음 이벤트는 t 1 또는 그 이후에 시작되어야 합니다.

예 1:

• 입력: 이벤트 = [[1,3,2],[4,5,2],[2,4,3]]
• 출력: 4
• 설명: 합이 2 2 = 4인 녹색 이벤트인 0과 1을 선택합니다.

예 2:

• 입력: 이벤트 = [[1,3,2],[4,5,2],[1,5,5]]
• 출력: 5
• 설명: 합이 5인 경우 이벤트 2를 선택하세요.

예 3:

• 입력: 이벤트 = [[1,5,3],[1,5,1],[6,6,5]]
• 출력: 8
• 설명: 합이 3 5 = 8인 경우 이벤트 0과 2를 선택합니다.

제약조건:

• 2 5
• 이벤트[i].length == 3
• 1 <= startTime_i <= endTime_i <= 10⁹
• 1 <= 값_i <= 10⁶

힌트:

1. 시작 시간을 기준으로 이벤트를 정렬하는 것이 어떻게 도움이 되나요? 종료 시간은 어떻습니까?
2. 우리가 선택한 간격과 교차하지 않는 간격의 최대 점수를 어떻게 빨리 얻을 수 있나요?

해결책:

다음 접근 방식을 사용할 수 있습니다.

접근하다

1. 종료 시간을 기준으로 이벤트 정렬:

   • 정렬은 이진 검색을 사용하여 겹치지 않는 이벤트를 효율적으로 찾는 데 도움이 됩니다.

2. 겹치지 않는 이벤트에 대한 이진 검색:

   • 이진 검색을 사용하여 현재 이벤트 시작 시간 전에 종료되는 최신 이벤트를 찾으세요. 이렇게 하면 겹치지 않게 됩니다.

3. Max Tracking을 사용한 동적 프로그래밍:

   • 정렬된 이벤트를 반복하면서 현재 이벤트까지의 이벤트 최대값을 유지합니다. 이를 통해 두 이벤트의 최대 합을 빠르게 계산할 수 있습니다.

4. 최대 합계 반복 및 계산:

   • 각 이벤트에 대해 다음을 사용하여 가능한 합계를 계산합니다.
     • 현재 이벤트만
     • 이진 검색을 사용하여 찾은 최고의 중복되지 않는 이벤트와 결합된 현재 이벤트입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2054. 겹치지 않는 두 가지 최고의 이벤트

  
  
  설명:




정렬:


이벤트는 종료 시간을 기준으로 정렬되어 중복되지 않는 마지막 이벤트를 효율적으로 검색할 수 있습니다.



이진 검색:


각 이벤트에 대해 이진 검색은 현재 이벤트가 시작되기 전에 종료되는 가장 늦은 이벤트를 결정합니다.



최대 추적:


현재 인덱스까지 이벤트의 최대값을 저장하는 maxUpTo 배열을 유지 관리합니다. 이렇게 하면 이전 지수의 최대값을 다시 계산하지 않아도 됩니다.



최대 합계 계산:


각 이벤트에 대해 해당 값과 겹치지 않는 가장 좋은 이벤트 값의 합을 계산합니다. 그에 따라 전역 최대 합계를 업데이트하세요.





  
  
  복잡성 분석




정렬: O(n log n)


각 이벤트에 대한 이진 검색: O(log n), n회 반복 → O(n log n)


전체: O(n log n)



이 솔루션은 효율적이며 제약 조건 내에서 잘 작동합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 두 가지 최고의 비중복 이벤트의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!