一个模板刷N题-treeMap解区间题

第一次刷题经验帖，表达能力比较差，求各位看官请拍。觉得有用的话，顺便求米~~~
第一题：LC1094:car-pooling
https://leetcode.com/problems/car-pooling/
给定一个数据trips，trips[0] , trips[1], trips[2]分表代表上车地点，下车地点和人数，要求返回汽车是否可以一趟运输完所有的乘客。我们可以模拟汽车的行驶过程，记录每一个上车以及下车地点车上的人数，最后判断每个上下车点人数是否超过capacity。由于上下车地点是排序的，可以使用treeMap这种数据结构，代码如下：
        

[Java] 纯文本查看 复制代码

TreeMap<Integer, Integer> map = new TreeMap();
   for (int[] trip : trips) {
    map.put(trip[1], map.getOrDefault(trip[1], 0) + trip[0]);
    map.put(trip[2], map.getOrDefault(trip[2], 0) - trip[0]);
   }
   int persons = 0;
   for (int k : map.keySet()) {
    persons += map.get(k);
    if(persons > capacity) return false;
   }
   return true;
    }

第二题：LC253:meeting-room-ii
https://leetcode.com/problems/meeting-rooms-ii/
给定一个会议区间列表，返回需要的会议室数量。
Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
和上一题其实很类似，上一题是给定区间trip，trip[2]代表权重。这一题meeting只有两个值，其实最有一个值是默认值1。Meeting[0], meeting[1]代表上下车地点，最有一个值表示每个地点上车1人，返回车上最多一共出现过多少人。代码如下：

游客，本帖隐藏的内容需要积分高于 20 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

第三、四、五题：my-calendar i, ii, iii
https://leetcode.com/problems/my-calendar-i/， 日程不能有冲突
https://leetcode.com/problems/my-calendar-ii/， 日程最多只有一次冲突
https://leetcode.com/problems/my-calendar-iii/， 返回日程最多出现过几次冲突
类似meeting-room-ii，出现最多冲突的日程次数即上一题中，最多需要的会议室：
my-calendar-iii代码如下
[mw_shl_code=java,true]TreeMap<Integer, Integer> map;

    public MyCalendar() {
        map = new TreeMap();
    }
    public int book(int start, int end) {
        int res = 0, count = 0;
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        for(int v : map.values()){
            count+=v;
            res = Math.max(res, count);
        }
        return res;
    }
my-calendar-ii代码：
public boolean book(int start, int end) {
        int count = 0;
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        boolean canBook = true;
        for(int v : map.values()){
            count+=v;
            if(count>2){//最多出现冲突日程不能大于2
                canBook = false;
                break;
            }
        }
        if(!canBook){
            map.put(start, map.get(start)-1);
            map.put(end, map.get(end)+1);
        }

        return canBook;
}



第六题：LC56. Merge Intervals
https://leetcode.com/problems/merge-intervals/
合并区间，一般做法是先排序再合并。如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理不了。但是treeMap可以：
代码如下：

[Java] 纯文本查看 复制代码

public int minMeetingRooms(int[][] intervals) {
     TreeMap<Integer, Integer> map = new TreeMap();
     for (int[] itv : intervals) {
      map.put(itv[0], map.getOrDefault(itv[0], 0)+1);
      map.put(itv[1], map.getOrDefault(itv[1], 0)-1);
     }
     int res = 0, count = 0;
     for (int v : map.values()) {
      count += v;
      res = Math.max(res, count);
     }
     return res; 
}[/hide]
第三、四、五题：my-calendar i, ii, iii
[url=https://leetcode.com/problems/my-calendar-i/]https://leetcode.com/problems/my-calendar-i/[/url]， 日程不能有冲突
[url=https://leetcode.com/problems/my-calendar-ii/]https://leetcode.com/problems/my-calendar-ii/[/url]， 日程最多只有一次冲突
[url=https://leetcode.com/problems/my-calendar-iii/]https://leetcode.com/problems/my-calendar-iii/[/url]， 返回日程最多出现过几次冲突
类似meeting-room-ii，出现最多冲突的日程次数即上一题中，最多需要的会议室：
my-calendar-iii代码如下
[mw_shl_code=java,true]TreeMap<Integer, Integer> map;

    public MyCalendar() {
        map = new TreeMap();
    }
    public int book(int start, int end) {
        int res = 0, count = 0;
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        for(int v : map.values()){
            count+=v;
            res = Math.max(res, count);
        }
        return res;
    }
my-calendar-ii代码：
public boolean book(int start, int end) {
        int count = 0;
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        boolean canBook = true;
        for(int v : map.values()){
            count+=v;
            if(count>2){//最多出现冲突日程不能大于2
                canBook = false;
                break;
            }
        }
        if(!canBook){
            map.put(start, map.get(start)-1);
            map.put(end, map.get(end)+1);
        }

        return canBook;
} 

第七题：LC1109. Corporate Flight bookings
https://leetcode.com/problems/corporate-flight-bookings/
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
给出起止航班号以及订阅数量，返回每个航班的订阅数量：

[Java] 纯文本查看 复制代码

public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];
        List<int[]> list = new ArrayList<>();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int[] itv : intervals){//添加区间节点的过程
            map.put(itv[0], map.getOrDefault(itv[0], 0)+1);
            map.put(itv[1], map.getOrDefault(itv[1], 0)-1);
        }
        int count = 0, start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
        for (int k : map.keySet()){
            count+=map.get(k);
            start = Math.min(start, k);
            end = Math.max(end, k);
            if (count==0){//关键：count==0代表区间闭合了，需要把刚刚闭合的区间添加到结果集中。可以类比字符串中左右括号的情况，遇到左括号+1，右括号-1。当count==0时，区间的括号是完全匹配的。
                list.add(new int[]{start, end});
                start = Integer.MAX_VALUE;
                end = Integer.MIN_VALUE;
            }
        }
        return list.toArray(new int[list.size()][2]);
}

由于给出的航班数是有限值n，可以使用counting sort代替treeMap进行排序，代码如下：

[Java] 纯文本查看 复制代码

public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] booking : bookings){
            map.put(booking[0], map.getOrDefault(booking[0], 0)+booking[2]);
            map.put(booking[1]+1, map.getOrDefault(booking[1]+1, 0)-booking[2]);
        }
        int prev = 0;
        for (int k : map.keySet()){
            map.put(k, map.get(k)+prev);
            prev = map.get(k);
        }
        for (int i=1;i<=n;i++){
            Integer booking = map.floorKey(i);
            if (booking!=null){
                res[i-1] = map.get(booking);
            }
        }
        return res;
    }

如果上面几题给的区间开始和截止点都比较小的话，也都可以使用数据代替treeMap进行排序。

这个模版的本质，还是start和end两个位置的频率统计，然后遍历结果以求得capacity / merge / verify。如果需要遍历的元素数量上限确定的话，可以用数组来代替treemap。

比如Car Pooling

[Java] 纯文本查看 复制代码

public boolean carPooling(int[][] trips, int capacity) {
        int stops[] = new int[1001]; 
        for (int[] t : trips) {
          stops[t[1]] += t[0];
          stops[t[2]] -= t[0];
        }
        for (int i = 0; i < stops.length; i++) {
            capacity -= stops[i];
            if (capacity < 0) return false;
        }
        return true;
    }

TreeMap的优势在于Flexible Length, 以及floorKey等接口，可以避免如1109题中的Corner case. 缺点在于每一个操作都是O(Log(n)), 很多情况下与数组相比TC会处于劣势。

很棒，感谢分享！

zea7ot 发表于 2020-08-24 18:10:35
我不太清楚你这里说的"这个"具体是指什么。

如果是使用楼主本帖描述的扫描线(Sweep Line)算法，那TreeMap几乎是是必须的。如果不是必须的，我个人也是强烈推荐的。

嗯嗯 我觉得你对扫描线算法的理解是对的 但是就对这两题而言 我们扫描过程不是由这个map决定的而是由那个for 循环 你看代码只有读值和插入对吧 其实这题的本质就是start 和 end 的频率统计 所以其实不需要treemap

为什么不用HashMap用TreeMap呢？

非常棒！

> 56 merge intervals 如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理不了。但是treeMap可以
排序也可以解，也非常清晰，就是57. Insert Interval， 代码如下：

[Java] 纯文本查看 复制代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        
        // corner case
        if ((intervals == null || intervals.length == 0)
            && (newInterval == null || newInterval.length == 0)) return new int[][]{};
        
        int i = 0;
        int n = intervals.length;
        int start = newInterval[0];
        int end = newInterval[1];
        
        // case 1: no overlap
        // intervals :     |_____|
        // [start, end] :               |______|
        //
        while (i < n && intervals[1] < start) {
            list.add(intervals);
            i++;
        }
        
        // case 2: overlap
        // intervals :     |_____| |___|
        // [start, end] :        |______|
        //
        while (i < n && intervals[0] <= end) {
            start = Math.min(start, intervals[0]);
            end = Math.max(end, intervals[1]);
            i++;
        }
        list.add(new int[]{start, end});
        
        // case 3: no overlap
        // intervals :               |_____|
        // [start, end] :     |______|
        //
        while (i < n) {
            list.add(intervals);
            i++;
        }
        return list.toArray(new int[0][]);
    }
}

仔细看了这个帖子的话，interval相关的所有问题都能解了! 非常感谢楼主！

一直有疑问，如果刷题用python， 然后发现题目要用到tree map 怎么办

话说java 有tree map, 但是python 需要先自己实现一下

scope 发表于 2020-1-21 23:53
为什么不用HashMap用TreeMap呢？

TreeMap 有排序

diamondsky 发表于 2020-1-22 00:15
非常棒！

> 56 merge intervals 如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理 ...

57的默认条件是Interval 数组已经排好序，而56并没有这个条件。但interval以数据流形式出现，每一步interval insert之后，整体数组保持有序。

感谢分享！

这个帖子总结的很好，和leetcode上的这个discussion异曲同工。https://leetcode.com/problems/me ... -Scheduling-Problem
759. Employee Free Time 也可以用这个模板，和merge interval思路相同。merge interval求的是时间戳上所有被占据的区间，而759求得是时间戳上没有被占据的间隙。

[Java] 纯文本查看 复制代码

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> res = new ArrayList<>();
        if (schedule == null || schedule.size() == 0) return res;
        TreeMap<Integer, Integer> calendar = new TreeMap<>();
        for (List<Interval> list : schedule) {
            if (list == null || list.size() == 0) continue;
            for (Interval i : list) {
                calendar.put(i.start, calendar.getOrDefault(i.start, 0) + 1);
                calendar.put(i.end, calendar.getOrDefault(i.end, 0) - 1);
            }
        }
        int count = 0;
        int start = -1;
        for (Map.Entry<Integer, Integer> entry : calendar.entrySet()) {
            count += entry.getValue();
            if (count == 0) start = entry.getKey();
            if (count > 0 && start != -1) {
                res.add(new Interval(start, entry.getKey()));
                start = -1;
            }
        }
        return res;
    }
}