13. Interval与扫描线

区间类的题目，很多可以用Greedy来做

Comparator的两种实现方法

• 一种是先Implements一个类，然后Arrays.sort(intervals, new newComparator);

  public class newComparator implements Comparator<Object>{
       public int compare(Object a, Object b) {
           Interval aa = (Interval) a;
           Interval bb = (Interval) b;
           return aa.start - bb.start;
       }
  }

• 另一种是写在Arrays.sort()里面，实践证明这种更快

  Arrays.sort(intervals, new Comparator<Interval>(){
            //compare by start time
            public int compare(Interval a, Interval b){
                return a.start - b.start;
            }
  });

Meeting Room

这题最简单的方法就是sort by start time,then check if(intervals[i].start < intervals[i-1].end) return false;

Meeting Rooms II

• 给定一堆meetings, 要求返回需要最少room的数量

• sort intervals by start time

• minHeap compare with end time

• for loop intervals, if cur.startTime < minHeap.peek().endTime, then push cur to heap, cnt++ ->NlogK

• res = max(cnt)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        //sort intervals by start time ->NlogN
        //minHeap compare with end time
        //for loop intervals, if cur.startTime < minHeap.peek().endTime, then push cur to heap, cnt++ ->NlogK
        //res = max(cnt)
        //Time: NlogN
        //Space: O(K)
        if (intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    return a[1] - b[1];
                }
                return a[0] - b[0];
            }
        });
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        int res = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (minHeap.isEmpty() || minHeap.peek()[1] > intervals[i][0]) {
                minHeap.offer(intervals[i]);
            } else {
                minHeap.poll();
                minHeap.offer(intervals[i]);
            }
            res = Math.max(res, minHeap.size());
        }
        
        return res;
    }
}

还有一种扫描线解法

Merge Interval

• sort intervals by start time

• iterate each interval, compare cur.startTime with prev.EndTime

• if cur.startTime < end, then end = Math.max(end, cur.endTime)

• else push [begin, end] to res

class Solution {
    /*
    sort intervals by start time
    iterate each interval, compare cur.startTime with prev.EndTime
    if cur.startTime < end, then end = Math.max(end, cur.endTime)
    else push [begin, end] to res
    
    */
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int begin = intervals[0][0], end = intervals[0][1];
        for (int i = 0; i < intervals.length; i++) {
            if(intervals[i][0] <= end) {
                end = Math.max(end, intervals[i][1]);
            } else {
                int[] interval = new int[2];
                interval[0] = begin;
                interval[1] = end;
                list.add(interval);
                begin = intervals[i][0];
                end = intervals[i][1];
            }
        }
        int[] interval = new int[2];
        interval[0] = begin;
        interval[1] = end;
        list.add(interval);
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i][0] = list.get(i)[0];
            res[i][1] = list.get(i)[1];
        }
        return res;
    }
    
    //05/05/21, while loop
    public int[][] merge(int[][] intervals) {
        //sort interval by start time in ascending order
        //[start,end], while (end >= curStart) -> end = curEnd and move to next
        Arrays.sort(intervals, new Comparator<int[]> () {
           @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        List<int[]> list = new ArrayList<>();
        
        int i = 0;
        while (i < intervals.length) {
            int start = intervals[i][0], end = intervals[i][1];
            int j = i+1;
            while (j < intervals.length && end >= intervals[j][0]) {
                end = Math.max(end, intervals[j][1]);
                j++;
            }
            int[] interval = new int[2];
            interval[0] = start;
            interval[1] = end;
            list.add(interval);
            i = j;
        }
        int[][] res = new int[list.size()][2];
        for (int k = 0; k < list.size(); k++) {
            res[k] = list.get(k);
        } 
        return res;
    }
}

Inset Interval

• 这题最简单的做法是把newInterval插到intervals里面，然后再调用上面的merge Interval的方法

• 但是鉴于此题有个前提Given a set of non-overlapping intervals，所以用merge interval的话可能会浪费很多时间

• 所以可以把intervals分成三部分，对于整个interval都在newinterval左边或者右边的我们可以直接add to res

• 所以只需要处理有overlapping的情况，这里有个技巧就是用while loop实现之前的三部分分类，改变newInterval的start和end值，直到当前的interval完全在newInterval的右边，没有任何交集

• 然后add newInterval, 再add the rest into res

• 这题对于space可以有优化，in place solultion,但是因为list.remove(i)是O(N)操作，所以时间上会有牺牲

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new LinkedList<>();

        int i = 0;
        while(i < intervals.size() && intervals.get(i).end < newInterval.start){
            res.add(intervals.get(i));
            i++;
        }
        while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
            newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
            newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
            i++;
        }
        res.add(newInterval);
        while(i < intervals.size()){
            res.add(intervals.get(i));
            i++;
        }
        return res;
    }
}

Summary Ranges

• 这题从算法上没啥好说的

• 就是注意corner case就好，比如[0,1] [7]

• 还有解体要有模块化的思路

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new LinkedList<>();
        if(nums == null || nums.length < 1) return res;
        int start = nums[0];
        int end = nums[0];
        //int i = 1;

        for(int i = 1; i < nums.length; i++){
            if(nums[i - 1] + 1 != nums[i]){
                String range = getRange(start, end);
                res.add(range);
                start = nums[i];
            }
            end = nums[i];
        }
        String last = getRange(start, end);
        res.add(last);
        return res;
    }
    //[2,3,4]
    //[7]
    private String getRange(int start, int end){
        StringBuilder sb = new StringBuilder();
        if(start == end){
            sb.append(start);
        }else if(start < end){
            sb.append(start);
            sb.append("->");
            sb.append(end);
        }
        return sb.toString();
    }
}

Missing Ranges(好题)

• 这题比summary ranges稍难，重在理清思路

• 有个简单的方法是用lower做runner

• 每次遍历num时，设upperBelow = num - 1,然后比较upperBelow和 lower的关系

• 然后记得update lower = num + 1

• 这样写的话题有个test case过不去[2147483647], lower = 0, upper = 2147483647。原因在于lower = num + 1之后就int overflow了，所以必须cast to long type

  public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new LinkedList<>();
        long low = (long) lower;
        long high = (long) upper;
        for(int num : nums){
           // if(lower > upper) break;
            long upperBelow = (long)num - 1;
            if(low == upperBelow){
                res.add((int)low + "");
            }else if(low < upperBelow){
                res.add((int)low + "->" + (int)upperBelow);
            }
            low = (long)num + 1;
        }
        if(low == high){
            res.add((int)low + "");
        }else if(low < high){
            res.add((int)low + "->" + (int) high);
        }
        return res;
    }

Data Stream as Disjoint Intervals

Skyline Problem