309. My Calendar II

🔗 LeetCode Problem: 731. My Calendar II
📊 Difficulty: Medium
🏷️ Topics: Design, Segment Tree, Binary Search, Ordered Set

Problem Statement

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all three 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 MyCalendarTwo class: - MyCalendarTwo() 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 triple booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input:
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output:
[null, true, true, true, false, true, true]

Explanation:
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True (single booking)
myCalendarTwo.book(50, 60); // return True (single booking)
myCalendarTwo.book(10, 40); // return True (creates one double booking [10,20))
myCalendarTwo.book(5, 15);  // return False (would create triple booking at [10,15))
myCalendarTwo.book(5, 10);  // return True (creates double booking [5,10))
myCalendarTwo.book(25, 55); // return True (creates double bookings)

Constraints: - 0 <= start < end <= 10^9 - At most 1000 calls will be made to book.

---

🌳 Visual Understanding - The Triple Booking Problem

Let's Discover This Problem Step by Step:

What's the difference from My Calendar I?

My Calendar I:
  ❌ ANY overlap (double booking)
  Only 1 booking allowed at any time

My Calendar II:
  ✓ Single booking OK
  ✓ Double booking OK (two overlapping events)
  ❌ Triple booking (three overlapping events)
  Maximum 2 bookings allowed at any time

Visual Discovery:

Let's walk through the example:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 1: book(10, 20)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Timeline:
  5    10   15   20   25
       |---------|

Single booking: [10,20)
Double bookings: none
Result: TRUE ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 2: book(50, 60)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Timeline:
  5    10   15   20   25   ...   50   55   60
       |---------|                |---------|

Single bookings: [10,20), [50,60)
Double bookings: none
Result: TRUE ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 3: book(10, 40)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Timeline:
  5    10   15   20   25   30   35   40
       | --------- |
       | --------- |← NEW

Overlaps with [10,20)!
  Overlap region: [10,20) (both events active)

Single bookings: [10,20), [50,60), [10,40)
Double bookings: [10,20) ← NEW!
Result: TRUE ✓ (double booking OK!)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 4: book(5, 15)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Timeline:
  5    10   15   20   25   30   35   40
  | ---------                   | ← NEW |
  | --------------------------- |
  | --------------------------- |

New [5,15) overlaps with:
  - [10,20): overlap = [10,15)
  - [10,40): overlap = [10,15)

Check: Would [10,15) be a TRIPLE booking?
  At x=10: [10,20), [10,40), [5,15) all active
  At x=14: [10,20), [10,40), [5,15) all active

  THREE events at same time!

Already have double booking [10,20)
New event would overlap this double booking at [10,15)
= TRIPLE BOOKING! ✗

Result: FALSE ✗

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 5: book(5, 10)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Timeline:
  5    10   15   20   25   30   35   40
  | ----                        | ← NEW |
  | --------------------------- |
  | --------------------------- |

New [5,10) overlaps with [10,40):
  Overlap = [5,10)

Does NOT overlap with existing double booking [10,20)!
  [5,10) ends at 10
  [10,20) starts at 10
  They just touch, no overlap!

Creates new double booking [5,10)
But no triple booking!

Result: TRUE ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 6: book(25, 55)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Timeline:
  5    10   15   20   25   30   35   40   45   50   55   60
  | ----                        |
  | --------------------------- |
  | --------------------------- |
  | --------------------------- | ← NEW |
  | ---------                   |

New [25,55) overlaps with:
  - [10,40): overlap = [25,40)
  - [50,60): overlap = [50,55)

Does NOT overlap with existing double bookings!
  - [10,20): 25 >= 20, no overlap
  - [5,10): 25 >= 10, no overlap

Creates new double bookings: [25,40), [50,55)
But no triple booking!

Result: TRUE ✓

The Key Insight:

We need to track TWO things:

1. All bookings (single)
   When new booking comes, check overlaps with these
   Create new double bookings

2. Double bookings (existing overlaps)
   When new booking comes, it CANNOT overlap with these!
   If it does → triple booking!

Algorithm:
  1. Check if new booking overlaps any DOUBLE booking
     → If YES: reject (would be triple)
  2. Find all overlaps with existing bookings
     → Add these overlaps as new double bookings
  3. Add new booking to all bookings

---

🧠 Discovering the Solution - Intuitive Approach

Let's Think Through This:

Question 1: What causes a triple booking?

Triple booking happens when:
  New booking overlaps with an EXISTING double booking

Example:
  Already have: [10,20), [10,40)
  Double booking: [10,20)

  Try to add [5,15):
    [5,15) overlaps [10,20) at [10,15)
    [10,20) is already a double booking
    → [10,15) would be TRIPLE!

So the check is:
  Does new booking overlap ANY existing double booking?

Question 2: How to track double bookings?

When we add a new booking, it might create new double bookings!

Example:
  Have: [10,20)
  Add: [15,25)

  They overlap at [15,20)
  This is a NEW double booking!

So when adding new booking:
  1. Check overlaps with all existing bookings
  2. Each overlap becomes a double booking
  3. Store these double bookings

Question 3: What data structure?

Need TWO lists:
  1. bookings: all single bookings
  2. doubleBookings: all double booked regions

For new booking [start, end):

  Step 1: Check against double bookings
    for each double in doubleBookings:
      if overlap(double, [start,end]):
        return FALSE  // Would be triple!

  Step 2: Find new double bookings
    for each booking in bookings:
      if overlap(booking, [start,end]):
        overlap_region = getOverlap(booking, [start,end])
        add overlap_region to doubleBookings

  Step 3: Add to bookings
    add [start,end) to bookings
    return TRUE

---

🟢 Approach: Two Lists (Bookings + Double Bookings)

💡 Intuition

Track two separate lists:
  1. bookings: ALL booked intervals
  2. doubleBookings: Intervals that are ALREADY double booked

For new booking:
  1. Check if it overlaps ANY double booking → reject if yes
  2. Find overlaps with existing bookings → add as double bookings
  3. Add to bookings list

This ensures we never create triple bookings!

🎨 Building the Solution

Helper Function: Get Overlap

// Get overlap between two intervals [a,b) and [c,d)
// Returns null if no overlap
private int[] getOverlap(int[] interval1, int[] interval2) {
    int start1 = interval1[0], end1 = interval1[1];
    int start2 = interval2[0], end2 = interval2[1];

    // Check if they overlap
    if (start1 >= end2 || start2 >= end1) {
        return null;  // No overlap
    }

    // Overlap exists
    int overlapStart = Math.max(start1, start2);
    int overlapEnd = Math.min(end1, end2);

    return new int[]{overlapStart, overlapEnd};
}

Main Implementation

import java.util.*;

class MyCalendarTwo {
    private List<int[]> bookings;
    private List<int[]> doubleBookings;

    public MyCalendarTwo() {
        bookings = new ArrayList<>();
        doubleBookings = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        int[] newBooking = new int[]{start, end};

        // Step 1: Check if new booking overlaps any DOUBLE booking
        // If yes, would create TRIPLE booking → reject!
        for (int[] doubleBooking : doubleBookings) {
            int[] overlap = getOverlap(doubleBooking, newBooking);
            if (overlap != null) {
                // Overlaps with existing double booking!
                // Would create triple booking!
                return false;
            }
        }

        // Step 2: Find overlaps with existing bookings
        // Each overlap becomes a new DOUBLE booking
        for (int[] booking : bookings) {
            int[] overlap = getOverlap(booking, newBooking);
            if (overlap != null) {
                // This overlap will be a double booking
                doubleBookings.add(overlap);
            }
        }

        // Step 3: Add new booking to all bookings
        bookings.add(newBooking);
        return true;
    }

    // Helper: Get overlap between two intervals
    private int[] getOverlap(int[] interval1, int[] interval2) {
        int start1 = interval1[0], end1 = interval1[1];
        int start2 = interval2[0], end2 = interval2[1];

        // No overlap if one ends before other starts
        if (start1 >= end2 || start2 >= end1) {
            return null;
        }

        // Overlap region
        int overlapStart = Math.max(start1, start2);
        int overlapEnd = Math.min(end1, end2);

        return new int[]{overlapStart, overlapEnd};
    }
}

🔍 Complete Dry Run

Calls: book(10,20), book(50,60), book(10,40), book(5,15), book(5,10)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 1: book(10, 20)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

bookings = []
doubleBookings = []

Step 1: Check against double bookings
  doubleBookings is empty → no conflicts

Step 2: Find overlaps with existing bookings
  bookings is empty → no overlaps

Step 3: Add to bookings
  bookings = [[10,20]]

Return: TRUE ✓

State:
  bookings = [[10,20]]
  doubleBookings = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 2: book(50, 60)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: Check against double bookings
  doubleBookings is empty → no conflicts

Step 2: Find overlaps with existing bookings
  [50,60) vs [10,20): 50 >= 20 → no overlap

Step 3: Add to bookings
  bookings = [[10,20], [50,60]]

Return: TRUE ✓

State:
  bookings = [[10,20], [50,60]]
  doubleBookings = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 3: book(10, 40)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: Check against double bookings
  doubleBookings is empty → no conflicts

Step 2: Find overlaps with existing bookings
  [10,40) vs [10,20):
    overlap = [max(10,10), min(40,20)] = [10,20] ✓
    Add [10,20] to doubleBookings

  [10,40) vs [50,60]:
    40 <= 50 → no overlap

Step 3: Add to bookings
  bookings = [[10,20], [50,60], [10,40]]

Return: TRUE ✓

State:
  bookings = [[10,20], [50,60], [10,40]]
  doubleBookings = [[10,20]]  ← NEW!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 4: book(5, 15)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: Check against double bookings
  [5,15) vs [10,20):
    overlap = [max(5,10), min(15,20)] = [10,15] ✓
    OVERLAP EXISTS!

    This would create TRIPLE booking at [10,15)!
    REJECT!

Return: FALSE ✗

State: (unchanged)
  bookings = [[10,20], [50,60], [10,40]]
  doubleBookings = [[10,20]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 5: book(5, 10)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: Check against double bookings
  [5,10) vs [10,20):
    5 >= 20? NO
    10 >= 10? YES → no overlap!

    [5,10) ends at 10
    [10,20) starts at 10
    They just TOUCH, no overlap!

Step 2: Find overlaps with existing bookings
  [5,10) vs [10,20]:
    10 >= 10? YES → no overlap (touch only)

  [5,10) vs [50,60]:
    10 <= 50 → no overlap

  [5,10) vs [10,40]:
    5 < 40 AND 10 > 10? NO
    10 >= 10? YES → no overlap (touch only)

Step 3: Add to bookings
  bookings = [[10,20], [50,60], [10,40], [5,10]]

Return: TRUE ✓

State:
  bookings = [[10,20], [50,60], [10,40], [5,10]]
  doubleBookings = [[10,20]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULTS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

[true, true, true, false, true] ✓

📊 Complexity Analysis

Time Complexity:

book(): O(n)
  Check double bookings: O(d) where d = number of double bookings
  Find new overlaps: O(n) where n = number of bookings

  In worst case, d can be O(n²) (all pairs overlap)
  But typically d << n

  Average: O(n)

Space Complexity: O(n)

bookings list: O(n)
doubleBookings list: O(n) in worst case

---

🎯 Key Insights Summary

The Three Critical Points:

1. Track Two Separate Lists

bookings: ALL booked intervals
doubleBookings: Regions with 2 overlapping bookings

This separation is THE key! 🔑

Why two lists?
  - bookings: check to create new double bookings
  - doubleBookings: check to prevent triple bookings

2. Order of Checks Matters

MUST check double bookings FIRST!

Wrong order:
  1. Add overlaps to double bookings
  2. Check against double bookings
  → Might add AFTER triple booking created!

Correct order:
  1. Check against double bookings (reject if overlap)
  2. Add overlaps to double bookings
  3. Add to bookings

3. Half-Open Interval Property

[a,b) and [b,c) do NOT overlap!

Example from dry run:
  [5,10) and [10,20):
    First ends at 10 (excluded)
    Second starts at 10 (included)
    They TOUCH but don't overlap!

This allows consecutive bookings! ✓

---

💡 Why This Approach Works - Deep Intuition

The Double Booking Tracking:

Question: Why track double bookings separately?

Answer: To detect triple bookings efficiently!

When new booking comes:
  If it overlaps a double booking:
    That overlap region would have 3 bookings!
    (2 from double + 1 new = 3 total)

  If it doesn't overlap any double booking:
    At most 2 bookings at any point
    (Existing singles + new = at most 2)

So checking against double bookings catches triples! ✨

Why We Add All Overlaps:

Every overlap with existing booking becomes double booking

Example:
  Have: [10,20), [15,25)
  Add: [12,22)

  [12,22) overlaps both:
    - [12,22) ∩ [10,20) = [12,20) → double booking
    - [12,22) ∩ [15,25) = [15,22) → double booking

  Both regions now have 2 bookings!
  Must track BOTH as double bookings!

Later booking might overlap one of these doubles!

---

⚠️ Common Mistakes

// Mistake 1: Wrong order of operations
for (int[] booking : bookings) {
    // Add overlaps first ❌
}
for (int[] doubleBooking : doubleBookings) {
    // Then check ❌
}
// ✓ CORRECT: Check double bookings FIRST!

// Mistake 2: Not using half-open interval logic
if (start1 <= end2 && start2 <= end1) { // ❌ Wrong for [a,b)
// ✓ CORRECT: Use strict <
if (start1 < end2 && start2 < end1) {

// Mistake 3: Modifying lists during iteration
for (int[] booking : bookings) {
    doubleBookings.add(...); // ⚠️ OK if iterating bookings
}
for (int[] doubleBooking : doubleBookings) {
    doubleBookings.add(...); // ❌ Concurrent modification!
}

// Mistake 4: Not returning false immediately
boolean hasTriple = false;
for (int[] doubleBooking : doubleBookings) {
    if (overlap) hasTriple = true; // ❌ Should return immediately!
}
// ✓ CORRECT:
if (overlap) return false;

// Mistake 5: Adding to bookings before checking doubles
bookings.add(newBooking); // ❌ Too early!
for (int[] doubleBooking : doubleBookings) {
    if (overlap) return false;
}
// ✓ CORRECT: Add AFTER all checks pass

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Book events allowing double but not triple bookings

Key Insight: Track bookings AND double bookings separately!

Algorithm: 1. Check new booking against ALL double bookings 2. If any overlap → reject (would be triple) 3. Find overlaps with existing bookings → add as doubles 4. Add new booking to bookings list

Why It Works: Double bookings list catches potential triples!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.List;

class MyCalendarTwo {
  // step 1: create 2 list
  // list1: has single booking window
  // list2: has double booking windows
  List<int[]> singleBookings;
  List<int[]> doubleBookings;

  public MyCalendarTwo() {
    singleBookings = new ArrayList<>();
    doubleBookings = new ArrayList<>();
  }

  public boolean book(int start, int end) {
    // step 2: check if this incoming interval overlaps
    // with any one of the double bookings (fail fast)
    for (int[] booking : doubleBookings) {
      int[] overlap1 = getOverlap(booking, start, end);
      if (overlap1 != null) {
        return false;
      }
    }

    // step 3: check if this incoming interval overlaps
    // with any one of the single booking windows. We can
    // merge this as double booking is accepted.
    // GOTCHA: Also, need to add in single bookings.
    for (int[] booking : singleBookings) {
      int[] overlap2 = getOverlap(booking, start, end);
      if (overlap2 != null) {
        doubleBookings.add(new int[] { overlap2[0], overlap2[1] });
      }
    }

    // step 4: if no overlap with either single or double booking
    // windows, add in single bookings list normally.
    singleBookings.add(new int[] { start, end });

    return true;
  }

  private int[] getOverlap(int[] booking, int start, int end) {
    // no overlap between (1,5) and (6,7) => 5 <= 6 (booking[1] <= start)
    // no overlap between (6,7) and (1,5) => 5 <= 6 (end <= booking[0])
    // overlap between (1,4) and (2,3) => both 4<=2 and 3<=1 fail
    // if no overlap, continue checking next booking.
    if (booking[1] <= start || end <= booking[0]) {
      return null;
    }

    // else return overlap
    // example overlap between (1,5) and (2,6) => (2,5)
    int[] overlap = new int[2];
    overlap[0] = Math.max(booking[0], start);
    overlap[1] = Math.min(booking[1], end);

    return overlap;
  }
}

public class Solution {
  public static void main(String[] args) {
    MyCalendarTwo mct = new MyCalendarTwo();

    System.out.println(mct.book(10, 20) == true);
    System.out.println(mct.book(50, 60) == true);
    System.out.println(mct.book(10, 40) == true);
    System.out.println(mct.book(5, 15) == false);
    System.out.println(mct.book(5, 10) == true);
    System.out.println(mct.book(25, 55) == true);
  }
}

🔑 Key Points

✓ Two lists: bookings + doubleBookings
✓ Check doubles FIRST (order matters!)
✓ Overlap: start < other.end AND other.start < end
✓ Overlap region: [max(starts), min(ends)]
✓ Half-open: touching intervals don't overlap
✓ Time: O(n), Space: O(n)

🎪 Memory Aid

"Two lists track, single and double!"
"Check doubles first, no triple trouble!"
"Overlaps become doubles, that's the bubble!"
"Half-open touch is fine, not a muddle!" ✨

---

🎉 Congratulations!

You've mastered My Calendar II!

What You Learned:

✅ Two-list strategy - Separate tracking
✅ Order of operations - Check before add
✅ Overlap detection - Finding intersections
✅ Half-open intervals - Touching vs overlapping
✅ Design extension - Building on Calendar I

The Beautiful Insight:

Calendar II → Track Double Bookings to Prevent Triples

The core insight:
  "Don't just track bookings"
  "Track double bookings too!"

  Why?
    New booking + double booking = TRIPLE
    So check against doubles first!

  Algorithm:
    1. Check doubles (prevent triple)
    2. Add overlaps as doubles
    3. Add to bookings

  This cleanly extends Calendar I!

This pattern appears in:
  - Resource allocation (max capacity)
  - Meeting room booking (room limits)
  - Concurrency control (max threads)
  - Any "bounded overlap" problem

Master this = Handle capacity constraints! ✨

Interview Mastery:

When asked about My Calendar II:

1. Understand: "Allow double but not triple bookings"

2. Difference from I: "Calendar I: no double
   Calendar II: allow double, prevent triple"

3. Key insight: "Track two lists:
   - All bookings
   - Double booked regions"

4. Why two lists: "New booking overlapping double
   would create triple. So check doubles first!"

5. Algorithm: "
   Step 1: Check against double bookings (reject if overlap)
   Step 2: Find overlaps with bookings (add as doubles)
   Step 3: Add to bookings"

6. Order matters: "MUST check doubles before adding!
   Otherwise might add after triple created."

7. Complexity: "O(n) per booking, O(n) space"

8. Half-open: "Remember [a,b) and [b,c) just touch,
   don't overlap!"

Shows extension and design skills! 💯

You've mastered the extension from Calendar I to Calendar II! This shows how to build on simpler problems - the two-list strategy is elegant and efficient! 🚀✨🎯