Skip to content

731. My Calendar II 👍

Approach 1: Brute Force

  • Time:
    • Constructor: $O(1)$
    • book(start: int, end: int): $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MyCalendarTwo {
 public:
  bool book(int start, int end) {
    for (const auto& [s, e] : overlaps)
      if (max(start, s) < min(end, e))
        return false;

    for (const auto& [s, e] : ranges) {
      const int ss = max(start, s);
      const int ee = min(end, e);
      if (ss < ee)
        overlaps.emplace_back(ss, ee);
    }

    ranges.emplace_back(start, end);
    return true;
  }

 private:
  vector<pair<int, int>> ranges;
  vector<pair<int, int>> overlaps;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class MyCalendarTwo {
  public boolean book(int start, int end) {
    for (int[] overlap : overlaps)
      if (Math.max(start, overlap[0]) < Math.min(end, overlap[1]))
        return false;

    for (int[] range : ranges) {
      final int maxStart = Math.max(start, range[0]);
      final int minEnd = Math.min(end, range[1]);
      if (maxStart < minEnd)
        overlaps.add(new int[] {maxStart, minEnd});
    }

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

  List<int[]> ranges = new ArrayList<>();
  List<int[]> overlaps = new ArrayList<>();
}

Approach 2: Ordered Map

  • Time:
    • Constructor: $O(1)$
    • book(start: int, end: int): $O(n\log n)$
  • Space: $O(n)$
 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 MyCalendarTwo {
 public:
  bool book(int start, int end) {
    ++timeline[start];
    --timeline[end];

    int activeEvents = 0;

    for (const auto& [_, count] : timeline) {
      activeEvents += count;
      if (activeEvents > 2) {
        if (--timeline[start] == 0)
          timeline.erase(start);
        if (++timeline[end] == 0)
          timeline.erase(end);
        return false;
      }
    }

    return true;
  }

 private:
  map<int, int> timeline;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MyCalendarTwo {
  public boolean book(int start, int end) {
    timeline.merge(start, 1, Integer::sum);
    timeline.merge(end, -1, Integer::sum);

    int activeEvents = 0;

    for (final int count : timeline.values()) {
      activeEvents += count;
      if (activeEvents > 2) {
        if (timeline.merge(start, -1, Integer::sum) == 0)
          timeline.remove(start);
        if (timeline.merge(end, 1, Integer::sum) == 0)
          timeline.remove(end);
        return false;
      }
    }

    return true;
  }

  private Map<Integer, Integer> timeline = new TreeMap<>();
}