贪心算法专题

题目：

        给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

        数组中的每个元素代表你在该位置可以跳跃的最大长度。

        判断你是否能够到达最后一个下标。

示例：

        输入：nums = [2,3,1,1,4]

        输出：true

        解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

贪心策略：

        向后遍历数组，每一步都更新可以到达的最远位置，如果最远位置包含了最后的元素，那么就返回true

class Solution {
    public boolean canJump(int[] nums) {
        int max=0;
        for(int i=0;i=i){
                //那就更新最远跳跃距离
                max=Math.max(max,i+nums[i]);
                //最远跳跃距离包含最后一点，就可以直接返回true了
                if(max>=nums.length-1){
                    return true;
                }
            //跳不到第i点那就永远也跳不过去
            }else{
                return false;
            }
        }
        return true;
    }
}

题目：

        给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

        你可以在满足 startDayi 

        请你返回你可以参加的 最大 会议数目。

示例：

        输入：events = [[1,2],[2,3],[3,4]]

        输出：3

        解释：你可以参加所有的三个会议。安排会议的一种方案如上图。

                        第 1 天参加第一个会议。

                        第 2 天参加第二个会议。

                        第 3 天参加第三个会议。

示例：

        输入：events= [[1,2],[2,3],[3,4],[1,2]]

        输出：4

贪心策略：

        优先选择会议结束时间早的

class Solution {
    public int maxEvents(int[][] events) {
        //按开始时间排序
        Arrays.sort(events, (a, b)->(a[0]-b[0]));
        //优先队列（小根堆），存会议结束的时间
        PriorityQueue queue = new PriorityQueue<>();

        int result = 0;
        int start = events[0][0];
        int index = 0;
        
        //还有会议没开始或还有会议没结束，就进入循环
        while(index < events.length || !queue.isEmpty()){
            //把开始时间相同的，放入堆中，比较结束时间，谁先结束就选谁
            while(index < events.length && events[index][0] == start){
                queue.offer(events[index][1]);
                index++;
            }
            //把开始时间之前已经结束的删除
            while(!queue.isEmpty() && queue.peek() < start){
                queue.poll();
            }

            //如果队列不空，还有会议没结束，那么队头，就是结束时间最早的会议，参加他
            if(!queue.isEmpty()){
                queue.poll();
                result++;
            }
            //下一天
            start++;
        }
        return result;
    }
}

题目：

        给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。 

示例 :

        输入: intervals = [[1,2],[2,3],[3,4],[1,3]]

        输出: 1

        解释: 移除 [1,3] 后，剩下的区间没有重叠。

贪心策略：

        如果区间之间冲突，就删除占用区间最大的那个

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //按照起始位置递增排序
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);
        int num=0;
        int i=0;
        for(int j=1;j=intervals[i][1]){
                //区间之间不冲突
                i=j;
            }else{
                if(intervals[j][1]