算法总结-使用 TreeMap 解决 My Calendar 问题

TreeMap 继承了 AbstractMap 类，同时实现了 NavigableMap 接口，其内部的实现是基于红黑树，存储的元素会按照 key 进行增序排序, 也可以在创建 TreeMap 的时候传入一个 Comparator 参数来定义如何排序。所以对于那些有排序需求的 key-value 数据就可以使用 TreeMap 来存储。

TreeMap的java api可以参考官方文档, 其中几个比较特殊的api有：

ceilingEntry(K key)：返回一个 key-value 的 Entry, 其 key 值大于等于传入的参数 key, 如果没有则返回 null。
floorEntry(K key): 返回一个 key-value 的 Entry, 其 key 值小于等于传入的参数 key, 如果没有则返回 null。
higherEntry(K key): 返回一个 key-value 的 Entry, 其 key 值大于传入的参数 key, 如果没有则返回 null。
lowerEntry(K key): 返回一个 key-value 的 Entry, 其 key 值小于传入的参数 key, 如果没有则返回 null。
firstEntry()：返回 key 值最小的 entry, 如果没有则返回 null。
lastEntry()：返回 key 值最大的 entry, 如果没有则返回 null。

上述的方法都是返回一个 key-value 的entry, 还有与其对应的 xxxKey()方法，可以直接返回对应的 key。

下面来看一下如何使用TreeMap来解决 My Calendar 的三个问题

My Calendar I

LeetCode 链接： https://leetcode.com/problems/my-calendar-i

题目描述：

在你的日历上预定一个时间段 [start, end)，判断当前的这个时间段是否和之前的有冲突，如果有冲突则直接返回 false，否则将这个时间段
添加到你的日历中并且返回 true。

解题思路：

新加入的时间段和之前已经预定好的时间段冲突方式有两种：

一个时间段包含了另外一个时间段

1 2	A: 2--------7 B: 3--5

一个时间段和另外一个时间段有一段重合的部分

1 2	C: 2------7 D: 5------9

时间段的开始和结束时间可以作为key - value 存入到 TreeMap 中, 如果时间段 B 是新加入的，则 A 就是其之前的时间段。如果A 的 value 大于 B 的 value 则就是A 包含了 B，如果A 的 value 大于 B的key, 但是小于B 的value 就成了 C 和 D 那种有一段冲突的情况。综合起来只需要判断 A 的value是否大于B的key即可，如果大于则存在冲突。

反过来如果B 是已经存在的时间段，而A是新加入的那么B就是A之后的那个时间段。同上面一样，还是需要判断A 的 value 和 B 的key值的大小关系来决定是否有冲突。

代码：

class MyCalendar {
    TreeMap<Integer, Integer> map = new TreeMap();
    public MyCalendar() {
        
    }
    
    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> pre = map.floorEntry(start);
        if(pre != null && pre.getValue() > start) return false;
        Map.Entry<Integer, Integer> next = map.ceilingEntry(start);
        if(next != null && next.getKey() < end) return false;
        map.put(start, end);
        return true;
    }
}

My Calendar II

LeetCode 链接：https://leetcode.com/problems/my-calendar-ii/

题目描述：

在往日历中预定新的时间段的时候，可以允许至多两个时间段的冲突，如果有3个时间段有共同的冲突则返回 false。

解题思路：

对于这道题目可以继续延用上一题的思路，如果使用 TreeMap来判断是否有3个时间段冲突呢？在这里可以创建两个 TreeMap, 第一个还是存储预定的时间段，而第二个则存储当前已经冲突的时间段，如果新加入的时间段和第二个map中已经冲突的时间段有冲突，则说明有3个时间段存在共同的冲突。在进行这个判断的时候可以复用上一题的代码。

代码：

class MyCalendarTwo {

    TreeMap<Integer, Integer> map = new TreeMap();
    TreeMap<Integer, Integer> overlapMap = new TreeMap();

    public MyCalendarTwo() {
        
    }
    
    public boolean book(int start, int end) {
        if(!canBook(start, end)) return false;

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            Integer overlapStart = Math.max(start, entry.getKey());
            Integer overlapEnd = Math.min(end, entry.getValue());
            if(overlapStart < overlapEnd) {
                // 存在冲突，更新 overlapMap
                overlapMap.put(overlapStart, overlapEnd);
            }
        }
        // 如果已经存在一个相同起点的冲突时间段，保留最长的那个
        map.put(start, Math.max(map.getOrDefault(start, 0), end));
        return true;
    }
    
    public boolean canBook(int start, int end) {
        Map.Entry<Integer, Integer> pre = overlapMap.floorEntry(start);
        if(pre != null && pre.getValue() > start) return false;
        Map.Entry<Integer, Integer> next = overlapMap.ceilingEntry(start);
        if(next != null && next.getKey() < end) return false;
        return true;
    }
}

解题思路2：

这一题还有另外一个解题思路。在 TreeMap 中，将 start 的 value 设为1，将 end 的 value 设为 -1。先将新的时间段添加到 map 中，然后从头开始遍历这个 TreeMap 并且累加 value 的值得到一个 sum，这样进入一个新的时间段的时候 sum 就会 +1，而出了一个时间段的时候 sum 就会-1。sum 值就代表了在当前的时间点有几个时间段存在冲突，所以只需要判断一下 sum 是否会大于2就可以了。另外需要记得当不能预定新的时间段的时候需要将其从map中删掉。

代码：

class MyCalendarTwo {

    TreeMap<Integer, Integer> map = new TreeMap();

    public MyCalendarTwo() {
        
    }
    
    public boolean book(int start, int end) {
        map.put(start, map.getOrDefault(start, 0) + 1);
        map.put(end, map.getOrDefault(end, 0) - 1);

        int sum = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            sum += entry.getValue();
            if(sum > 2){
                // 发现了有个3个冲突的时间段，删掉之前添加的 start 和 end
                if(map.get(start) == 1) {
                    map.remove(start);
                } else {
                    map.put(start, map.get(start) -1);
                }

                if(map.get(end) == -1) {
                    map.remove(end);
                } else {
                    map.put(end, map.get(end) + 1);
                }
                return false;
            }
        }
        return true;
    }
}

My Calendar III

LeetCode 链接： https://leetcode.com/problems/my-calendar-iii

题目描述：

在添加新的预定时间段之后，需要返回存在共同冲突最多的的时间段数目。如最多有3个时间段有相同的冲突，则返回3。

题目分析：

这道题虽然标记是 Hard 难度，但是在用第二种方法解了上一题后这一题就会感觉非常简单。直接在遍历的过程中记录下最大的 sum 值就可以。

代码：

class MyCalendarThree {

    TreeMap<Integer, Integer> map = new TreeMap();

    public MyCalendarThree() {
        
    }
    
    public int book(int startTime, int endTime) {
        map.put(startTime, map.getOrDefault(startTime, 0) + 1);
        map.put(endTime, map.getOrDefault(endTime, 0) - 1);

        int sum = 0;
        int max = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
            max = Math.max(max, sum);
        }
        return max;
    }
}

总结

TreeMap作为一种特殊的 Map，使用得可能不如 HashMap 广泛，但是其在处理有排序需求的 key-value 数据有着极大的优势。当遇到有排序需求并且每个位置有着额外的信息的问题时，就可以考虑使用 TreeMap 来解决。