Leetcode.com problem 729: "My Calendar I"

James S. Plank

Fri Aug 5 09:59:36 AM EDT 2022

Problem Statement.
Success Rate (as of July, 2019): 57.1%
This is a medium problem.
main.cpp - A driver that you can use for testing.
tests.sh - A testing script.
answers.txt - The correct output of the testing script.

This is a classic use of the lower_bound method of C++ sets and maps.

In case Leetcode's servers are down

Here is a summary of the problem:

You are to implement a class called myCalendar, which has two public methods:

A constructor without parameters.
A method book():
bool book(int start, int end);

You call book() with a starting and ending time of a meeting that you want to book. Your data structure needs to keep track of your meetings, and if it's possible to book the meeting, your book() method should add the meeting to the data structure and return true. Otherwise, it should return false.

The times are integers between 0 and 10⁹, and there will be at most 1000 calls to book in a test.

Code and examples

The code in main.cpp gives you a command-line tool to test your implementation. It accepts the following commands:

BOOK start end: This will call the book method and print out whether it is true or false.
RAND seed num: This will create num random book() calls. The start times will be between 0 and 10⁹, and the end times will be between 1 and 10⁶ past start. It prints out the number of true and the number of false responses.
RAND-P seed num: This does the same as RAND, but it prints the individual calls.

So:

UNIX> ( echo BOOK 10 20 ; echo BOOK 0 5 ; echo BOOK 7 11 ; echo BOOK 5 10 ) | ./a.out
TRUE
TRUE
FALSE
TRUE
UNIX> echo RAND-P 11 10 | a.out
749653431 750153829 TRUE
219272843 220264038 TRUE
447348371 447509815 TRUE
141543152 141750265 TRUE
516427696 517005756 TRUE
402840984 403610499 TRUE
132900213 133003825 TRUE
516453320 517374582 FALSE
980791656 981416244 TRUE
716132944 716848105 TRUE
9 1
UNIX> echo RAND 10 1000 | ./a.out
673 327
UNIX>

Hints

This is a perfect use of a map. Keys are times, and vals are either 0 or 1. When you call book() and you determine that the booking works, then you insert the start time into the map with a value of 1, and the end time with a value of 0. If a start time coincides with a previous end time, or vice versa, then you delete the time from the map.

In this way, you can use lower_bound calls to determine whether or not the booking is valid.

Let's do the example from above:

UNIX> ( echo BOOK 10 20 ; echo BOOK 0 5 ; echo BOOK 7 11 ; echo BOOK 5 10 ) | ./a.out

The map starts as empty.
After book(10,20), then the map contains { (10,1), (20,0) }.
After book(0,5), then the map contains { (0,1), (5,0), (10,1), (20,0) }.
When you call book(7,11), then you will discover that there is a meeting that starts at time 10, which would overlap with this meeting. So you return false.
After book(5,10), then the map contains { (0,1) , (20,0) } -- you have deleted 5 and 10 from the map.

To help you think -- you can call lower_bound on both start and end, or you can just call it on start, and examine the adjacent iterators. I'm not going to hand-hold you more than that. The running time complexity of book() will be O(log n), where n is the number of elements in the map.