Leetcode

My Calendar II

May 26, 2022 by aAshish

Approach 1: Brute Force

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

C++

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

JAVA

 
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)

C++

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

JAVA

 
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) {
        timeline.merge(start, -1, Integer::sum);
        if (timeline.get(start) == 0)
          timeline.remove(start);
        timeline.merge(end, 1, Integer::sum);
        if (timeline.get(end) == 0)
          timeline.remove(end);
        return false;
      }
    }

    return true;
  }

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