732. My Calendar III #

Problem #

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one 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 K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this:

MyCalendarThree cal = new MyCalendarThree();

MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

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

Problem Summary #

Implement a MyCalendar class to store your schedule arrangements, and you can always add new schedule arrangements.

MyCalendar has a book(int start, int end) method. It means adding a schedule arrangement from start to end. Note that the time here is a half-open interval, namely [start, end), the range of real numbers x is, start <= x < end. When K schedule arrangements have some overlap in time (for example, K schedule arrangements are all at the same time), a K-booking occurs. Each time the MyCalendar.book method is called, return an integer K, representing the largest K-booking.

Please call the MyCalendar class according to the following steps: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Notes:

For each test case, the MyCalendar.book function will be called no more than 400 times.
When calling the function MyCalendar.book(start, end), the value range of start and end is [0, 10^9].

Solution #

Design a calendar class. Each time a schedule is added, it displays in real time the maximum number of overlapping schedules in the current calendar. For example, if 3 schedules are arranged within a period of time, while at all other times there are only 0, 1, or 2 schedules, then output 3.
After getting this problem, you will immediately think of a segment tree. Since the problem only involves adding schedules, this problem is not difficult. This problem is also similar to problem 699, but there are differences. In problem 699, Tetris blocks will stack up one after another, while in this problem, the Tetris blocks also stack up, but if there is a gap underneath a block, the block will break. For example: add the intervals [10,20], [10,40], [5,15], [5,10] in order. If following the rules of problem 699, the block [5,10] would fall onto [5,15], making the height 4. But this problem is about schedules, and schedules are different. There are 3 schedules in the interval [5,15], but other parts do not have 3 schedules, so the part [5,10] of the third block [5,15] will “break” and fall down. The fourth block is still [5,10], and it falls into the position where the third block broke off; the height of the two of them together is 2.
Construct a segment tree. Here a tree is used to construct it; if an array is used, a very large amount of space needs to be allocated. When the left and right boundaries of the interval are exactly the same as the query boundaries, then increment the count; otherwise do not add, and continue dividing the interval. Use the left boundary of the interval as the standard for dividing the interval, because the left boundary of the interval is open and the right side is closed. The count value of an interval is based on the count of the left boundary of the interval. Still using the example above, the count of [5,10) is based on 5, count = 2, and the count of [10,15) is based on 10, count = 3. A maximum value also needs to be dynamically maintained. The implementation of this segment tree is relatively simple.
Similar problems include: problem 715, problem 218, and problem 699. Problem 715 is interval update to a fixed value (not increase/decrease), problem 218 can use a sweep line, and problem 732 is similar to problem 699, also a Tetris problem, but the Tetris blocks in problem 732 will “break”.

Code #


package leetcode

// SegmentTree732 define
type SegmentTree732 struct {
	start, end, count int
	left, right       *SegmentTree732
}

// MyCalendarThree define
type MyCalendarThree struct {
	st        *SegmentTree732
	maxHeight int
}

// Constructor732 define
func Constructor732() MyCalendarThree {
	st := &SegmentTree732{
		start: 0,
		end:   1e9,
	}
	return MyCalendarThree{
		st: st,
	}
}

// Book define
func (mct *MyCalendarThree) Book(start int, end int) int {
	mct.st.book(start, end, &mct.maxHeight)
	return mct.maxHeight
}

func (st *SegmentTree732) book(start, end int, maxHeight *int) {
	if start == end {
		return
	}
	if start == st.start && st.end == end {
		st.count++
		if st.count > *maxHeight {
			*maxHeight = st.count
		}
		if st.left == nil {
			return
		}
	}
	if st.left == nil {
		if start == st.start {
			st.left = &SegmentTree732{start: start, end: end, count: st.count}
			st.right = &SegmentTree732{start: end, end: st.end, count: st.count}
			st.left.book(start, end, maxHeight)
			return
		}
		st.left = &SegmentTree732{start: st.start, end: start, count: st.count}
		st.right = &SegmentTree732{start: start, end: st.end, count: st.count}
		st.right.book(start, end, maxHeight)
		return
	}
	if start >= st.right.start {
		st.right.book(start, end, maxHeight)
	} else if end <= st.left.end {
		st.left.book(start, end, maxHeight)
	} else {
		st.left.book(start, st.left.end, maxHeight)
		st.right.book(st.right.start, end, maxHeight)
	}
}

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