Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

731. My Calendar II

Time: Constructor: $O(1)$, book(start: int, end: int): $O(n^2)$

Space: $O(n)$

			


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;
};




			


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<>();
}




			


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;
};