. 내 달력Ⅰ

729. 나의 달력Ⅰ

난이도:중

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

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

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

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

MyCalendar 클래스 구현:

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

예 1:

• 입력:

  ["MyCalendar", "book", "book", "book"]
  [[], [10, 20], [15, 25], [20, 30]]

• 출력:

  [null, true, false, true]

• 설명:

  MyCalendar myCalendar = new MyCalendar();
  myCalendar.book(10, 20); // return True
  myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
  myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

제약조건:

• 0 9
• 최대 1000통의 전화예약 가능합니다.

힌트:

1. 이벤트를 정렬된 간격 목록으로 저장합니다. 충돌하는 이벤트가 없으면 새 이벤트를 추가할 수 있습니다.

해결책:

각 이벤트를 저장하고 예약하기 전에 새 이벤트가 기존 이벤트와 충돌하는지 확인해야 합니다. 최대 1000번의 예약 호출이 허용되므로 이벤트를 목록에 저장하고 이를 반복하여 새 이벤트를 예약할 때 중복 여부를 확인할 수 있습니다.

계획:

1. 이벤트 저장: 각 항목이 예약된 시간 간격을 나타내는 [시작, 종료] 쌍인 목록을 유지 관리합니다.
2. 충돌 확인: 새 이벤트를 추가하기 전에 예약된 이벤트 목록을 반복하여 새 이벤트가 기존 이벤트와 충돌하는지 확인합니다. 새 이벤트의 시작 시간이 기존 이벤트의 종료 시간보다 짧고 새 이벤트의 종료 시간이 기존 이벤트의 시작 시간보다 큰 경우 중복이 발생합니다.
3. 예약 이벤트: 충돌이 발견되지 않으면 예약 목록에 새 이벤트를 추가합니다.

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

<?php class MyCalendar {
    /**
     * @var array
     */
    private $events;

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

    /**
     * Books an event if it does not cause a double booking
     *
     * @param Integer $start
     * @param Integer $end
     * @return Boolean
     */
    function book($start, $end) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * $obj = MyCalendar();
 * $ret_1 = $obj->book($start, $end);
 */

// Example Usage:
$myCalendar = new MyCalendar();
var_dump($myCalendar->book(10, 20)); // true, no conflicts, booking added
var_dump($myCalendar->book(15, 25)); // false, conflict with [10, 20]
var_dump($myCalendar->book(20, 30)); // true, no conflicts, booking added
?>

설명:

1. 생성자(__construct): 예약된 모든 이벤트를 추적하기 위해 빈 배열 $events를 초기화합니다.

2. 예약 기능(도서):

   • 새로운 이벤트의 시작과 끝이 필요합니다.
   • 이전에 예약된 이벤트 목록을 반복하고 중복되는 부분이 있는지 확인합니다.
     • 기존 이벤트가 끝나기 전에 새 이벤트가 시작되고($start 기존 이벤트가 시작된 후에 종료되면($end > $bookedStart) 중복이 발생합니다.
   • 겹치는 부분이 발견되면 함수는 false를 반환하며 이는 이벤트를 예약할 수 없음을 의미합니다.
   • 충돌이 발견되지 않으면 이벤트가 $events 배열에 추가되고 함수는 true를 반환하여 성공적인 예약을 나타냅니다.

시간 복잡도:

• 이벤트 예약: 각 예약 호출에는 이전에 예약된 모든 이벤트와 비교하여 새 이벤트를 확인하는 작업이 포함됩니다. 이로 인해 각 예약 작업에 대해 O(n)의 시간 복잡도가 발생합니다. 여기서 n은 이전에 예약된 이벤트 수입니다.
• 공간 복잡도: 배열에 최대 n개의 이벤트를 저장하므로 공간 복잡도는 O(n)입니다.

예제 연습:

1. 첫 예약(책(10, 20)):

   • 이전 이벤트가 없어 [10, 20] 이벤트가 성공적으로 예약되었습니다.
   • 출력: true

2. 두 번째 예약(책(15, 25)):

   • 새 이벤트 [15, 25]는 시간 간격(15는 10과 20 사이)이 중복되어 이전에 예약된 이벤트 [10, 20]과 충돌합니다.
   • 출력: 거짓

3. 세 번째 예약(도서(20, 30)):

   • 새 이벤트 [20, 30]은 새 이벤트의 시작 시간이 첫 번째 이벤트 종료 시간과 정확히 일치하므로 [10, 20]과 겹치지 않습니다(반 열린 간격이므로 겹치지 않음).
   • 출력: true

이 간단한 접근 방식은 명확성과 정확성을 유지하면서 최대 1000개의 이벤트를 효율적으로 처리합니다.

연락처 링크

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

위 내용은 . 내 달력Ⅰ의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!