253. Meeting Rooms II

• 253. Meeting Rooms II
  • Description
  • Solution
    • TLE Solution

Description

Here

Solution

没啥技巧，就是容易错，再撸一遍。

TLE Solution

之所以TLE，原因有两个，因为duplicate一个map，非常糟糕； 这个remove操作不duplicate，会throw error，但可以用iterator鸡贼过去，

  public int minMeetingRooms(Interval[] intervals) {
    final TreeMap<Interval, Integer> map = new TreeMap<>(new Comparator<Interval>() {
      @Override
      public int compare(Interval o1, Interval o2) {
        return Integer.compare(o1.end, o2.end);
      }
    });
    int minMeetingRoom = 0;
    map.put(new Interval(0, Integer.MAX_VALUE), 0);
    for (Interval i : intervals) {
      i.end--; // make inclusive
      final Map<Interval, Integer> tailMap = new TreeMap<>(map.tailMap(
          new Interval(i.start, i.start)));
      for (Map.Entry<Interval, Integer> e : tailMap.entrySet()) {
        final Interval interval = e.getKey();
        final int count = e.getValue();
        if (interval.start > i.end) break;

        final int intervalStart = interval.start, intervalEnd = interval.end,
            iStart = i.start, iEnd = i.end;
        map.remove(interval);

        if (intervalStart < iStart) {
          map.put(new Interval(intervalStart, iStart - 1), count);
        }
        if (iEnd < intervalEnd) {
          map.put(new Interval(iEnd + 1, intervalEnd), count);
        }
        // i.start <= interval.start && interval.end <= i.end;
        map.put(new Interval(Math.max(iStart, intervalStart), Math.min(iEnd, intervalEnd)), count + 1);
        minMeetingRoom = Math.max(minMeetingRoom, count + 1);
      }
    }
    return minMeetingRoom;
  }