56. Merge Intervals

首先Specific Sort所给的Range List,按照start time 从小到大排列。然后使用Last代表上一个range，如果形成了单独的range加入result list然后更新range pointer

代码写的好首先思路要易懂清晰 可以类比链表的链接 ~ 我们在链接新的链表的时候 需要和前面的node建立一种联系

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        //check the size of the given list if it is less or equal than 1 then return 
        int n = intervals.size();
        if(n <= 1)return intervals;

        //sort the list according to the start time of the Interval
        Collections.sort(intervals,new Comparator<Interval>(){
            @Override 
            public int compare(Interval i1,Interval i2){
                return i1.start - i2.start;
            }
        });

        List<Interval> result = new ArrayList<Interval>();
        Interval pre = intervals.get(0);

        //compare and merge between prev and current intervals in the list 
        for(int i = 1;i < n;i++){
            Interval cur = intervals.get(i);
            if(cur.start <= pre.end){
                pre.end = Math.max(cur.end,pre.end);
            }
            else{
                result.add(pre);
                pre = cur;
            }
        }
        //add the last part
        result.add(pre);
        return result;
    }
}

57. Insert Interval

这道题第二次写的时候脱了半天一堆bug 本来想的是维护一个Pre Node 然后比较前后 但是代码里分支条件过多 不好操作

参考思路 这里还是需要额外的空间存储结果 因为维护原来的List也是需要删除的操作 分为三个部分

1. 没有交叉的部分 insert.start > node.end 一直推进node 并且append到最终list
2. 开始交叉 更新node的start和end 直到和下一个node不交叉为止
3. 剩余的node 全部append

时间：access the element only once O(N)

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        //find where to start insert 
        int len = intervals.size();
        List<Interval> result = new ArrayList();
        if(intervals.size() == 0)  
        {  
            result.add(newInterval); 
            return result; 
        }  
        int i = 0;
        while (i < len && intervals.get(i).end < newInterval.start){
            result.add(intervals.get(i++));
        }

        if(i < len)newInterval.start = Math.min(newInterval.start, intervals.get(i).start);  

        while(i < len && intervals.get(i).start <= newInterval.end){
            newInterval.end = Math.max(intervals.get(i).end,newInterval.end);
            i++;
        }
        result.add(newInterval);

        while(i < len){
            result.add(intervals.get(i++));
        }
        return result;
    }
}

252. Meeting Room

按照起始start collection sort 每次比较的时候更新最大的end(我们需要和前面的所有比较)

NLog(N)

public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return true;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        int end = intervals[0].end;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i].start < end) {
                return false;
            }
            //compare to the largest end among all precessors 
            end = Math.max(end,intervals[i].end);
        }
        return true;
    }
}

253. Meeting Rooms II

Keep a min Heap of end time? Sort the intervals by start time. If the current start time is larger than the polled out min end time which means no more meeting rooms(use the same) else we need a double meeting rooms

Greedy..

O(NlogN)

public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int num = intervals.length;
        if(num == 0 || num == 1){
            return num;
        }
        //sort the intervals by start time 
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        //
        PriorityQueue<Integer> q =  new PriorityQueue<Integer>();
        q.offer(intervals[0].end);
        int count = 1;
        for(int i = 1;i < num;i++){
            if(intervals[i].start >= q.peek()){ //如果没有冲突
                q.poll();
            }
            else{
                count++;
            }
            q.offer(intervals[i].end);
        }
        return count;
    }
}

163. Missing Ranges

这类问题总是写不好 关键是corner case的处理 代码写出来一点不简洁

Continuous Range (DrawBridge 电面)

自己简直傻到爆 明明写对的题 结果还是紧张写半天 哭泣while loop+move forward the pointer