Interval类

Interval类的greedy题，基本上涉及的是在sort或者priorityqueue中的comparator里，各个interval之间的相对位置怎么排。

Non-overlapping Intervals

这题根据Interval.end来排序，把小的end放在前面。如果当前的Interval.start大于prevInterval.end的话，把当前这个Interval给移除去，因为前一个Interval.end根据我们的排序规则已经是最小的。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval a, Interval b) {
                if (a.end != b.end) {
                    return a.end - b.end;
                } else {
                    return b.start - a.start;
                }
            }
        });

        Interval prev = intervals[0];
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            Interval current = intervals[i];
            if (prev.end <= current.start) {
                prev = current;
            } else {
                count++;
            }
        }
        return count;
    }
}

Minimum Number of Arrows to Burst Balloons

先排序，把Interval.start小的排在前面。每次看当前的interval.start有没有比前一个interval.end要大，如果有的话就要另起一只箭了，否则就是缩小箭的range。

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }

        Arrays.sort(points, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            }
        });

        int min = points[0][0], max = points[0][1];
        int count = 1;
        for (int i = 1; i < points.length; i++) {
            if (max < points[i][0]) {
                count++;
                min = points[i][0];
                max = points[i][1];
            } else {
                min = Math.max(min, points[i][0]);
                max = Math.min(max, points[i][1]);
            }
        }
        return count;
    }
}

Meeting Rooms II

这题我比较熟悉的做法是扫描线，这里用greedy的思想去做sorting来解这题。

先把数组根据了Interval.start来排序，然后我们有一个heap，heap的comparator是把interval.end小的放在前面。每当新进来一个meeting的时候，如果heap里end最小的值小于等于当前的start的话，我们只需要update这个heap.peek().end的值就可以了。否则，就说明了，heap里end最小的值都超出了当前的start，那就需要新加一个meeting room了。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval a, Interval b) {
                if (a.start != b.start) {
                    return a.start - b.start;
                } else {
                    return a.end - b.end;
                }
            }
        });

        Queue<Interval> queue = new PriorityQueue<Interval>(new Comparator<Interval>(){
            public int compare(Interval a, Interval b) {
                return a.end - b.end;
            }
        });

        queue.offer(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (queue.peek().end <= intervals[i].start) {
                Interval interval = queue.poll();
                interval.end = intervals[i].end;
                queue.offer(interval);
            } else {
                queue.offer(intervals[i]);
            }
        }
        return queue.size();
    }
}