729. My Calendar I #

Problem #

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return 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.

Your class will be called like this:

MyCalendar cal = new MyCalendar();

MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

• The number of calls to MyCalendar.book per test case will be at most 1000.
• In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

Problem Summary #

Implement a MyCalendar class to store your schedule. If there are no other events during the time to be added, this new event can be stored.

MyCalendar has a book(int start, int end) method. It means adding an event from start to end. Note that the time here is a half-open interval, i.e. [start, end), the range of real numbers x is  start <= x < end.

When two events have some overlap in time (for example, both events are at the same time), a double booking occurs.

Each time the MyCalendar.book method is called, if the event can be successfully added to the calendar without causing a double booking, return true. Otherwise, return false and do not add the event to the calendar.

Please call the MyCalendar class as follows: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Explanation:

• For each test case, the MyCalendar.book function will be called at most 100 times.
• When calling the function MyCalendar.book(start, end), the range of values for start and end is [0, 10^9].

Solution Ideas #

• The requirement is to implement a scheduling function. If there is a scheduling conflict, return false; if there is no conflict, return true.
• There are multiple solutions to this problem. The first solution can use an approach similar to problem 34. First sort each interval, then use binary search in this collection to find the last interval whose left value is smaller than the left value of the current interval to be compared. If found, then determine whether it can be inserted (check whether the right endpoint is smaller than the left endpoint of the next interval). The time complexity of this method is O(n log n).
• The second solution is to generate a BST. When inserting into the tree, first exclude cases where insertion is not possible, such as overlapping intervals. Then, based on the left value of the interval, insert recursively; each insertion will continue to check whether the intervals overlap. Until insertion is impossible, return false. The time complexity of the entire search is O(log n).

Code #

package leetcode

// Solution 1 Binary search tree
// Event define
type Event struct {
	start, end  int
	left, right *Event
}

// Insert define
func (e *Event) Insert(curr *Event) bool {
	if e.end > curr.start && curr.end > e.start {
		return false
	}
	if curr.start < e.start {
		if e.left == nil {
			e.left = curr
		} else {
			return e.left.Insert(curr)
		}
	} else {
		if e.right == nil {
			e.right = curr
		} else {
			return e.right.Insert(curr)
		}
	}
	return true
}

// MyCalendar define
type MyCalendar struct {
	root *Event
}

// Constructor729 define
func Constructor729() MyCalendar {
	return MyCalendar{
		root: nil,
	}
}

// Book define
func (this *MyCalendar) Book(start int, end int) bool {
	curr := &Event{start: start, end: end, left: nil, right: nil}
	if this.root == nil {
		this.root = curr
		return true
	}
	return this.root.Insert(curr)
}

// Solution 2 Quicksort + binary search
// MyCalendar define
// type MyCalendar struct {
// 	calendar []Interval
// }

// // Constructor729 define
// func Constructor729() MyCalendar {
// 	calendar := []Interval{}
// 	return MyCalendar{calendar: calendar}
// }

// // Book define
// func (this *MyCalendar) Book(start int, end int) bool {
// 	if len(this.calendar) == 0 {
// 		this.calendar = append(this.calendar, Interval{Start: start, End: end})
// 		return true
// 	}
// 	// Quicksort
// 	quickSort(this.calendar, 0, len(this.calendar)-1)
// 	// Binary search
// 	pos := searchLastLessInterval(this.calendar, start, end)
// 	// If the last element is found, need to check end
// 	if pos == len(this.calendar)-1 && this.calendar[pos].End <= start {
// 		this.calendar = append(this.calendar, Interval{Start: start, End: end})
// 		return true
// 	}
// 	// If it is not the element at the beginning or end, also need to check whether this interval can be inserted into the original array (check whether both the start point and end point can be inserted)
// 	if pos != len(this.calendar)-1 && pos != -1 && this.calendar[pos].End <= start && this.calendar[pos+1].Start >= end {
// 		this.calendar = append(this.calendar, Interval{Start: start, End: end})
// 		return true
// 	}
// 	// If the element is smaller than the first element, insert it at the beginning
// 	if this.calendar[0].Start >= end {
// 		this.calendar = append(this.calendar, Interval{Start: start, End: end})
// 		return true
// 	}
// 	return false
// }

// func searchLastLessInterval(intervals []Interval, start, end int) int {
// 	low, high := 0, len(intervals)-1
// 	for low <= high {
// 		mid := low + ((high - low) >> 1)
// 		if intervals[mid].Start <= start {
// 			if (mid == len(intervals)-1) || (intervals[mid+1].Start > start) { // Find the last element less than or equal to target
// 				return mid
// 			}
// 			low = mid + 1
// 		} else {
// 			high = mid - 1
// 		}
// 	}
// 	return -1
// }

/**
 * Your MyCalendar object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */