My Calendar Iii - Leetcode Solution

Problem Statement:

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:

MyCalendarThree cal = new MyCalendarThree(); cal.book(10, 20); // returns 1 cal.book(50, 60); // returns 1 cal.book(10, 40); // returns 2 cal.book(5, 15); // returns 3 cal.book(5, 10); // returns 3 cal.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.

It is not possible to have a 4-booking since the limit of K is 3.

Solution:

Approach: Segment Tree

In this approach, we gonna use a Segment Tree to store the booking intervals. We will keep a counter to count the number of intervals within each node of the segment tree. This counter will help us to find the maximum number of intersection intervals.

Algorithm:

1. First, we will create a class named SegmentTree that will represent a Segment Tree.

2. Define the methods,

   • build(int node, int start, int end)

   • update(int node, int start, int end, int left, int right)

   • query(int node, int start, int end, int left, int right)

3. Then, we will create a class named MyCalendarThree.

4. Define the method,

   • book(int start, int end) -> We will use the Segment Tree's update method to store the booking intervals. This will automatically update the count of all the intervals within the current node. We will then query this node to find the maximum number of intersection intervals.

Implementation:

class SegmentTree { int[] tree; int[] lazy;

public SegmentTree(int n) { tree = new int[4n]; lazy = new int[4n]; }

private void push(int node, int start, int end) { if(lazy[node] != 0) { tree[node] += lazy[node]; if(start != end) { lazy[2node] += lazy[node]; lazy[2node+1] += lazy[node]; } lazy[node] = 0; } }

/** Build segment tree **/ public void build(int node, int start, int end) { if(start == end) tree[node] = 0; else { int mid = (start + end) / 2; build(2node, start, mid); build(2node+1, mid+1, end); tree[node] = 0; } }

/** Update range **/ public void update(int node, int start, int end, int left, int right) { push(node, start, end); if(start > end || start > right || end < left) return; if(start >= left && end <= right) { lazy[node]++; push(node, start, end); return; } int mid = (start + end) / 2; update(2node, start, mid, left, right); update(2node+1, mid+1, end, left, right); tree[node] = Math.max(tree[2node], tree[2node+1]); }

/** Query range **/ public int query(int node, int start, int end, int left, int right) { push(node, start, end); if(start > end || start > right || end < left) return 0; if(start >= left && end <= right) return tree[node]; int mid = (start + end) / 2; int l = query(2node, start, mid, left, right); int r = query(2node+1, mid+1, end, left, right); return Math.max(l, r); } }

class MyCalendarThree { SegmentTree segmentTree; int max;

public MyCalendarThree() { segmentTree = new SegmentTree(2000000); max = 0; }

public int book(int start, int end) { // Add current booking to Segment Tree segmentTree.update(1, 0, 999999, start, end-1); // Query the Segment Tree to find the maximum count of bookings over all intervals max = Math.max(max, segmentTree.query(1, 0, 999999, start, end-1)); return max; } }

Time Complexity:

The time complexity of the update and query operations of the Segment Tree is O(logn), where n is the size of the Segment Tree.

In this problem, we need to perform these operations for every booking, so the time complexity for n bookings is O(nlogn).

Space Complexity:

The space complexity of the Segment Tree is O(n), where n is the size of the Segment Tree.

Overall, the space complexity is O(n).

1