. 마이캘린더II

731. 마이캘린더II

난이도:중

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

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

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

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

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 9
• 최대 1000통의 전화예약 가능합니다.

힌트:

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

해결책:

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

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

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

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

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

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

<?php class MyCalendarTwo {
    /**
     * @var array
     */
    private $singleBookings;
    /**
     * @var array
     */
    private $doubleBookings;

    /**
     */
    function __construct() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param Integer $start
     * @param Integer $end
     * @return Boolean
     */
    function book($start, $end) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * $obj = MyCalendarTwo();
 * $ret_1 = $obj->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";
?>

설명:

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

2. 책 기능(책):

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

시간 복잡도:

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

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

연락처 링크

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

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

• 링크드인
• 깃허브

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