领英电面挂经

领英的电面，面试官是国人大哥.

题目是这样的

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

实际上就是这个离口的原题

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

。

my solution with idea is similar to meeting roomII.


class MyIntervals {

    TreeMap<Integer, Integer> map;
    public MyIntervals(){
        map = new TreeMap<>();
    }

    public void add(int start, int end) {
        map.put(start, map.getOrDefault(start,0)+1);
        map.put(end, map.getOrDefault(end,0)-1);
    }

    public int getTotal(int start, int end){
        int cnt = 0;
        int begin=map.firstKey();
        int ans=0;
        for (int key: map.keySet()){
            if (map.get(key)>0 && cnt==0){
               begin = key;
            }
            if (map.get(key)<0 && cnt+map.get(key)==0){
                if (!(end<=begin || key<=start)){
                    ans += Math.min(end,key) - Math.max(begin,start);
                }
            }
            cnt += map.get(key);
        }
        return ans;

    }  
}

Aaron97 发表于 2019-2-28 07:19
我目前想到的是用TreeMap来存储,TreeMap默认是按照key进行升序排列,所以排序问题就解决了,如果有存在一个st ...

我没太看懂你要怎么加所有的value list里的值. 你是指的map里的key是start, value是list of end? 然后你把每个list里的最大的interval取出来然后和第二个value list里的最大值merge吗？因为每个list里肯定是从固定start到某一个值 所以只需要最大的end? 所以我没懂为什要用一个list来存end.

还有,用这个算法的话 假设只有一个interval start=1, end=10. 当我们叫get_total(2, 10)返回的是0吗？我记得这种情况是8 (sorry, 这个电面时间隔的有点久, 具体我有点忘记是不是这样算的了, 也有可能是按你这样只算start, end之内存在的interval 而不算之前interval的后一段).

是leetcode原题吗？

我目前想到的是用TreeMap来存储,TreeMap默认是按照key进行升序排列,所以排序问题就解决了,如果有存在一个start对应多个end的情况,存成TreeMap<Integer, List<Integer>>的形式;这样子add的方法基本解决了.至于get_total,找到key值在[start,end]之间对应的value list.然后加起来好了.不知道这样子是否符合题目的要求.还请楼主po出更多的信息

joseph1992 发表于 2019-2-28 10:15
我没太看懂你要怎么加所有的value list里的值. 你是指的map里的key是start, value是list of end? 然后你 ...

感觉可以用TreeMap, value 可以是最大的end。你说的这个情况，如果map里面没有start，就找lowerKey和higherKey

同意楼上用TreeMap的想法。可以用start 做为 key, TreeMap会自动排序好， value 用Interval.  对于add function, 如果没有对应的start, 直接在TreeMap中加入；否则将当前Interval.end取相同start所有intervals的最大值。
get_total 就要遍历 start, end之间的subtree.

看起来不难，感谢分享

这不就是丢盒子高频题merge interval - streaming也叫bittorrent. 最小堆的方法这里不行，二叉树可行。就是维护个根据start time排序的二叉树，每次二叉搜索相应位置，然后merge

补充内容 (2019-3-1 16:28):
哎，现在电面真是nontrivial了, 差不多得了

这题应该是treemap.