729. My Calendar I

Problem

Tags: Binary Search, Design, Segment Tree, Ordered Set

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
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.

Constraints:

0 <= start < end <= 10^9
At most 1000 calls will be made to book.

Code

C

// 729. My Calendar I (9/1/53956)
// Runtime: 104 ms (62.50%) Memory: 22.34 MB (54.17%) 

typedef struct Event {
    int start;
    int end;
} Event;

typedef struct MyCalendar {
    Event *events;
    int size;
} MyCalendar;

MyCalendar* myCalendarCreate() {
    MyCalendar *calendar = malloc(sizeof(MyCalendar));
    calendar->events = malloc(sizeof(Event) * 1000);
    calendar->size = 0;
    return calendar;
}

bool myCalendarBook(MyCalendar* calendar, int start, int end) {
    // 把已經建立的事件都做一次碰撞測試
    for(int i = 0; i < calendar->size; i++) {
        Event event = calendar->events[i];
        // 如果新事件開始比舊事件開始早，但結束在舊事件開始後，一定會撞到
        if (start < event.start && end > event.start) {
            return false;
        }
        // 如果新事件開始在舊事件時間範圍內，也一定會撞到
        else if (start >= event.start && start < event.end) {
            return false;
        }
    }

    // 如果沒有撞到，就把新事件加入
    Event new_event = { start, end };
    calendar->events[calendar->size++] = new_event;
    return true;
}

void myCalendarFree(MyCalendar* calendar) {
    free(calendar->events);
    free(calendar);
}

/**
 * Your MyCalendar struct will be instantiated and called as such:
 * MyCalendar* obj = myCalendarCreate();
 * bool param_1 = myCalendarBook(obj, start, end);
 
 * myCalendarFree(obj);
*/

JS

// 729. My Calendar I (10/14/53410)
// Runtime: 164 ms (83.97%) Memory: 47.40 MB (94.66%) 

/** MyCalendar.book
 * @param {number} start 
 * @param {number} end
 * @return {boolean}
 */
class MyCalendar {
    constructor() {
        this.events = [];
    }
    
    book(start, end) {
        let left = 0; 
        let right = this.events.length - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (this.events[mid][0] < end && this.events[mid][1] > start) return false;
            else if (this.events[mid][1] <= start) right = mid - 1;
            else left = mid + 1;
        }
        this.events.splice(left, 0, [start, end]);
        return true;
    }
};

/** 
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */

# 729. My Calendar I

# Problem

# Code

# C

# JS

729. My Calendar I

Problem

Code

C

JS