#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/interval-problems/my-calendar-i-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/interval-problems/my-calendar-i-implementation

Repovive

My Calendar I - Implementation - Interval Problems | Greedy Algorithms | Repovive

Repovive.

Greedy Algorithms8 sections · 317 units14h total

Open in Course

My Calendar I - Implementation

The code

Here is the simple solution:

class MyCalendar
 bookings := []

 function book(start, end)
 for each (s, e) in bookings
 if start < e and s < end then
 return false
 bookings.add((start, end))
 return true

Two intervals $[s_1, e_1)$ and $[s_2, e_2)$ overlap if and only if $s_1 < e_2$ and $s_2 < e_1$ . This is the standard overlap check.

Time: $O(n)$ per booking. Space: $O(n)$ total.