Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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.

Solution

Method 1 - Using Treemap storing endtime as key

  • TreeMap is utilised because it sorts its keys in natural ascending order for integers.
  • The map’s key represents the end time, and the value corresponds to the start time.
  • TreeMap is also chosen for its higherEntry method, which retrieves the next higher key compared to a given value (here, “start”).
  • For example, in TreeMap {1=One, 2=Two, 3=Three, 4=Four, 5=Five}, higherEntry(3) returns 4=Four.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class MyCalendar {
    private final TreeMap<Integer,Integer> calendar;
    public MyCalendar() {
       calendar = new TreeMap<>();
    }
    public boolean book(int start, int end) {
	    // pair where endTime in map
	    // is greater than provided start time
        Map.Entry<Integer,Integer> higherPair = calendar.higherEntry(start);
        // if pair exists and start time of pair
        // is less than proided endtime
        boolean isCollision = higherPair != null && end > higherPair.getValue();
        if(isCollision) {
	        return false;
        }
        calendar.put(end, start);
        return true;
    }
}

Method 2 - Using TreeMap and start time as key

  • Rather than using endTime as the key and startTime as the value, we can use startTime as the key and endTime as the value.
  • Floor entry refers to the preceding event with the closest lower value.
  • Ceiling entry refers to the subsequent event with the closest higher value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class MyCalendar {
    final TreeMap<Integer, Integer> calendar;

    public MyCalendar() {
        calendar = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        // Condition for checking start time
        // if current start time is lower than its lower entry end time
        // that means overlapping hence return false.
        if(calendar.floorEntry(start) != null && start < calendar.floorEntry(start).getValue())
            return false;

        // condition for checking end time
        // if current end time is greater than its next event start time
        // means overlapping hence return false.

        if(calendar.ceilingEntry(start) != null && end > calendar.ceilingEntry(start).getKey())
            return false;

        calendar.put(start, end);
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class MyCalendar {

	TreeMap<Integer, Integer> map;

	public MyCalendar() {
		map = new TreeMap<Integer, Integer> ();
	}

	public boolean book(int start, int end) {

		Integer floorKey = map.floorKey(start);
		Integer ceilKey = map.ceilingKey(start);

		if (floorKey != null && start<map.get(floorKey)) {
			return false;
		}

		if (ceilKey != null && end > ceilKey) {
			return false;
		}

		map.put(start, end);
		return true;
	}
}

Method 2 - Using Segment Tree

%%