. 마이캘린더II

731. 마이캘린더II

난이도:중

주제: 배열, 이진 검색, 디자인, 세그먼트 트리, 접두사 합계, 순서 집합

캘린더로 사용할 프로그램을 구현하고 계십니다. 이벤트를 추가해도 3중 예약이 발생하지 않는 경우 새 이벤트를 추가할 수 있습니다.

트리플 예약은 세 가지 이벤트에 비어 있지 않은 교차점이 있는 경우에 발생합니다(예: 어떤 순간이 세 이벤트 모두에 공통적임).

이벤트는 반개방 간격[시작, 종료)의 예약을 나타내는 정수 시작 및 종료 쌍, 시작 <= x < 끝.

MyCalendarTwo 클래스 구현:

• MyCalendarTwo() 달력 개체를 초기화합니다.
• boolean book(int start, int end) 3중 예약을 발생시키지 않고 이벤트를 캘린더에 성공적으로 추가할 수 있으면 true를 반환합니다. 그렇지 않으면 false를 반환하고 일정을 캘린더에 추가하지 않습니다.

예 1:

• 입력:

  ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
  [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

• 출력:

  [null, true, true, true, false, true, true]

• 설명:

  MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
  myCalendarTwo.book(10, 20); // return True, The event can be booked.
  myCalendarTwo.book(50, 60); // return True, The event can be booked.
  myCalendarTwo.book(10, 40); // return True, The event can be double booked.
  myCalendarTwo.book(5, 15);  // return False, The event cannot be booked, because it would result in a triple booking.
  myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
  myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

제약조건:

• 0 <= 시작 < 종료 <= 10⁹
• 최대 1000통의 전화예약 가능합니다.

힌트:

1. 두 개의 정렬된 간격 목록을 저장합니다. 하나의 목록은 최소한 한 번 예약된 모든 시간이고, 다른 목록은 확실히 이중 예약된 모든 시간입니다. 이중 예약 중 충돌하는 것이 없으면 예약이 성공하며 그에 따라 단일 및 이중 예약을 업데이트해야 합니다.

해결책:

두 가지 예약 목록을 유지해야 합니다.

1. 단일 예약: 한 번 예약된 모든 이벤트를 추적하는 목록입니다.
2. 이중 예약: 이중 예약된 모든 이벤트를 추적하는 목록입니다.

새로운 이벤트가 요청되면 3중 예약이 발생하는지 확인해야 합니다. 그렇게 하려면:

• 먼저 새로운 이벤트가 이중 예약 목록의 간격과 겹치는지 확인합니다. 그럴 경우 3중 예약이 발생하므로 이벤트를 추가할 수 없습니다.
• 이중 예약과 중복되는 내용이 없으면 단일 예약 목록을 확인하고 새 이벤트와 기존 이벤트의 중복을 이중 예약에 추가합니다. 목록.

마지막으로 이벤트가 두 검사를 모두 통과하면 단일 예약 목록에 추가됩니다.

이 솔루션을 PHP로 구현해 보겠습니다. 731. 나의 달력 II

book($start, $end);
 */


// Example Usage
$calendar = new MyCalendarTwo();
echo $calendar->book(10, 20) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(50, 60) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(10, 40) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(5, 15) ? 'true' : 'false'; // false
echo "\n";
echo $calendar->book(5, 10) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(25, 55) ? 'true' : 'false'; // true
echo "\n";
?>






  
  
  설명:



생성자(__construct): 단일 예약과 이중 예약을 저장하기 위해 두 개의 빈 배열로 달력 개체를 초기화합니다.

책 기능(책):


이벤트의 시작과 끝을 담당하는 함수입니다.
먼저 이벤트가 doubleBookings 목록의 간격과 겹치는지 확인합니다. 만약 그렇다면, 삼중 예약이 발생하기 때문에 함수는 false를 반환합니다.
트리플 부킹이 없을 경우, 싱글 부킹 목록의 이벤트와 중복되는지 확인합니다. 발견된 중복 항목은 이제 이중 예약을 나타내므로 doubleBookings 목록에 추가됩니다.
마지막으로 이벤트가 SingleBookings 목록에 추가되고 함수가 true를 반환합니다.





  
  
  시간 복잡도:



각 예약 작업의 시간 복잡도는 대략 O(n)입니다. 여기서 n은 지금까지 이루어진 예약 수입니다. 이는 각 예약에 대해 SingleBookings 및 doubleBookings 목록 모두에서 이전 예약을 모두 확인해야 할 수 있기 때문입니다.


이 솔루션은 문제 제약 조건에 따라 최대 1000번의 책 기능 호출을 효율적으로 처리합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 . 마이캘린더II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!