Interval 类问题中最常用的技巧，就是自定义 IntervalComparator，把输入按照 startTime 升序排序。

对于任意两个区间A与B，如果

A.end > B.start 并且

A.start < B.end

则 A 与 B 重叠。

按 start 排序后，数组有了单调性，上面的判断条件就简化成了 A.end > B.start 则一定重叠.

排序后的 Interval 扫描过程中，为了保证正确性，要格外小心多个 Interval 在同一 x 时，处理的先后顺序，比如 skyline problem.

扫描线算法

某个时间点最多的数量

拆解Interval，开始的时候count++，end的时候count—-，找出max的count

把区间拆开，按时间轴来排序

Number of Airplanes in the Sky

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

只去看扫描线和线段有交点的时候。 飞机的起飞和降落会改变交点的个数。

class Solution {
    class Point implements Comparable<Point> {
        int time;
        int status;

        public Point(int t, int s) {
            this.time = t;
            this.status = s;
        }

        public int compareTo(Point other) {
            if(this.time == other.time) {
                return this.status - other.status;
            }   
            return this.time - other.time;
        }    
    }   

    public int countOfAirplanes(List<Interval> airplanes) {        
        List<Point> list = new ArrayList<>();
        for(Interval in : airplanes) {
            list.add(new Point(in.start, 1));
            list.add(new Point(in.end, 0));
        }
        Collections.sort(list);

        int count = 0;
        int max = 0;

        for(Point p : list) {
            if(p.status == 1) {
                count++;
                max = Math.max(max, count);
            } else {
                count--;
            }
        }
        return max;   
    }
}

Meeting Rooms

Given an array of meeting time intervals consisting of start and end times, determine if a person could attend all meetings.

题意：是否Intervals是有重叠的地方

PQ的解法，按照start time排序，然后扫描如果有一个前一个的结束时间大于后一个的开始时间，就返回false.

public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        // sort 
        if(intervals == null || intervals.length == 0) {
            return true;
        }
        Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                if(i1.start == i2.start) {
                    return i1.end - i2.end;
                }
                return i1.start - i2.start;
            }
        };

        Arrays.sort(intervals, comp);

        for(int i = 0; i < intervals.length - 1; i++) {
            if(intervals[i].end > intervals[i + 1].start) {
                return false;
            }
        }
        return true;
    }
}

Non-overlapping Intervals

找出让所有intervals都不重合需要去除的点的数量。

这题需要用贪心算法来做： 贪心体现在按end排队以后，选越小的end time，越有可能不重合。 maintain count and lastEnd

• 按照end来sort
• 如果不重合就更新lastEnd, 并且count++，计算最大不重合的数量
• ans is len - count

public class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
           @Override
           public int compare(Interval i1, Interval i2) {
               return i1.end - i2.end;
           }
        });

        int count = 1;
        int lastEnd = 0;

        for(int i = 1; i < intervals.length; i++) {
            if(intervals[lastEnd].end <= intervals[i].start) {
                count++;
                lastEnd = i;
            }
        }

        return intervals.length - count;
    }
}

Meeting Rooms 2 (snapchat)

找到需要的最小的会议间的数量。

Snapchat高频题，也是FB的高频题

扫描线算法。需要注意的是如果有两个 interval 首尾相接，要把结束的那个排在 array 的前面，先把房间腾出来；否则的话会认为收尾相接的两个 meeting 需要占 2 个房间，这是错误的。

public class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

public class Solution {
    private class Point {
        int time;
        boolean isStart;
        public Point(int time, boolean isStart) {
            this.time = time;
            this.isStart = isStart;
        }
    }


    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;

        List<Point> points = new ArrayList<>();

        for(int i = 0; i < intervals; i++) {
            points.add(new Point(intervals[i].start, true));
            points.add(new Point(intervals[i].end, false));
        }

        Collections.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                if(p1.time == p2.time) return a.isStart ? 1 : -1;
                return p1.time - p2.time;
            }
        });

        int maxCount = 0;
        int count = 0;
        for(Point pt : points) {
            if(pt.isStart) count++;
            else count--;
            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}

(FB) follow-up: 如何返回重叠最多的那个区间？

当前 maxOverlap 创造新高的时候，存下 start 的时间戳，因为这是所有重合区间中 start 时间最晚的一个；

继续扫描，看到新的 end 的时候，存下这个 end 的时间戳，因为它是重合区间里 end 时间最早的一个；

二者之间，就是具体的 max overlap 区间。

PQ的做法

PQ里面记录的是最近结束的meeting 如果之后的会议的startTime 是晚于之前的endTime,那么merge 两个intervals。否则就把两个会议都加入PQ.

public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        // sort 
        if(intervals == null || intervals.length == 0) {
            return 0;
        }

        Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                if(i1.start == i2.start) {
                    return i1.end - i2.end;
                }

                return i1.start - i2.start;
            }
        };

        Arrays.sort(intervals, comp);

        PriorityQueue<Interval> pq = new PriorityQueue<Interval>(intervals.length,new Comparator<Interval>() {
           public int compare(Interval i1, Interval i2) {
               return i1.end - i2.end;
           } 
        });

        pq.offer(intervals[0]);

        for(int i = 1; i < intervals.length; i++) {
            // find the eariliest end meeting
            Interval meeting = pq.poll();

            // the first starting meeting after end
            if(meeting.end <= intervals[i].start) {
                meeting.end = intervals[i].end;
            } else {
                pq.offer(intervals[i]);
            }

            // don't forget to put meeting back
            pq.offer(meeting);
        }

        return pq.size();
    }
}

Skyline Problem

用一堆点来描述一系列大楼的outline

扫描线算法，因为outline只可能发生在每一段 start/end的边界上，因此以每个edge的位置和高度排序， 然后扫描

当有几个大楼重叠的时候，如何快速获得较大的值呢？用Heap来做。

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        List<int[]> result = new ArrayList<>();

        if(buildings == null || buildings.length == 0 || buildings[0].length == 0) return result;

        for(int[] building : buildings) {
            // add start point
            heights.add(new int[]{building[0], -building[2]});
            // add end point
            heights.add(new int[]{building[1], building[2]});
        }

        Collections.sort(heights, (a, b) -> {
            if(a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));

        // make it more consistent
        // can add the end point to result
        // 0 can stand for the ground
        pq.offer(0);
        int prev = 0;

        for(int[] height : heights) {
            if(height[1] < 0) {
                pq.offer(-height[1]);
            } else {
                // at the end point, remove the height from pq
                pq.remove(height[1]);
            }

            int cur = pq.peek();

            // reach a edge, check if the height has change
            if(cur != prev) {
                result.add(new int[]{height[0], cur});
                prev = cur;
            }
        }

        return result;

    }
}

因为heap的remove操作是O(N)的，所以时间复杂度是O(N ^ 2)

为了进一步优化时间复杂度，我们可以用TreeMap 来做，因为treemap 的所有操作都是O(log n) 我们应该用 height 做 Key，因为同一座建筑左右墙 height 相等，就可以实现查找。即使有多座 height 一样的左墙，我们也只需要用 count 做 value，把当前 height 的墙数减一即可。