D
DevExCode

LeetCode 731: My Calendar II Solution

Master LeetCode problem 731 (My Calendar II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use a similar approach to the "My Calendar I" problem but with an additional helper structure to keep track of double bookings. We will maintain two lists - one for regular bookings and another for double bookings. When booking an event, we will check if it overlaps with any existing double bookings. If it does, we return false. Otherwise, we update the double bookings list accordingly.

Algorithm:

  1. Initialize two lists - one for regular bookings and one for double bookings.
  2. For each booking request:
    • Check if the booking overlaps with any double bookings. If it does, return false.
    • Check if the booking overlaps with any regular bookings. If it does, add the overlapping interval to the double bookings list.
    • If no overlaps, add the booking to the regular bookings list.
  3. If all bookings are successful, return true.

Time Complexity:

  • Each booking operation involves iterating over the existing bookings, resulting in O(n) time complexity per booking, where n is the number of existing bookings.

Space Complexity:

  • O(n) where n is the number of total bookings.

:

Solution Code

class MyCalendarTwo {
    List<int[]> calendar;
    List<int[]> overlaps;

    public MyCalendarTwo() {
        calendar = new ArrayList<>();
        overlaps = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] interval : overlaps) {
            if (Math.max(interval[0], start) < Math.min(interval[1], end)) {
                return false;
            }
        }

        for (int[] interval : calendar) {
            if (Math.max(interval[0], start) < Math.min(interval[1], end)) {
                overlaps.add(new int[]{Math.max(interval[0], start), Math.min(interval[1], end)});
            }
        }

        calendar.add(new int[]{start, end});
        return true;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 731 (My Calendar II)?

This page provides optimized solutions for LeetCode problem 731 (My Calendar II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 731 (My Calendar II)?

The time complexity for LeetCode 731 (My Calendar II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 731 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 731 in Java, C++, or Python.

Back to LeetCode Solutions