贪心算法

区间问题：

区间问题肯定按照区间的起点或者终点进行排序。

435. 无重叠区间

题目描述：

贪心算法 - 图1

思路

正确的思路其实很简单，可以分为以下三步：

1、从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。

2、把所有与 x 区间相交的区间从区间集合 intvs 中删除。

3、重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

把这个思路实现成算法的话，可以按每个区间的 end 数值升序排序，因为这样处理之后实现步骤 1 和步骤 2 都方便很多，如下 GIF 所示：

贪心算法 - 图2

现在来实现算法，对于步骤 1，由于我们预先按照 end 排了序，所以选择 x 是很容易的。关键在于，如何去除与 x 相交的区间，选择下一轮循环的 x 呢？

由于我们事先排了序，不难发现所有与 x 相交的区间必然会与 x 的 end 相交；如果一个区间不想与 x 的 end 相交，它的 start 必须要大于（或等于）x 的 end：

贪心算法 - 图3

代码：

  1. class Solution {
  2.     public int eraseOverlapIntervals(int[][] intervals) {
  3.         int n = intervals.length;
  4.         return n - intervalSchedule(intervals);
  5.     }
  7.     // 区间调度算法，算出 intvs 中最多有几个互不相交的区间
  8.     int intervalSchedule(int[][] intvs) {
  9.         if (intvs.length == 0) return 0;
  10.         // 按 end 升序排序
  11.         Arrays.sort(intvs, new Comparator<int[]>() {   //手写不要用快捷键看看写不写的出来
  12.             public int compare(int[] a, int[] b) {
  13.                 return a[1] - b[1];
  14.             }
  15.         });
  16.         // 至少有一个区间不相交
  17.         int count = 1;
  18.         // 排序后，第一个区间就是 x
  19.         int x_end = intvs[0][1];
  20.         for (int[] interval : intvs) {
  21.             int start = interval[0];
  22.             if (start >= x_end) {
  23.                 // 找到下一个选择的区间了
  24.                 count++;
  25.                 x_end = interval[1];
  26.             }
  27.         }
  28.         return count;
  29.     }
  30. }

452. 用最少数量的箭引爆气球

题目描述：

贪心算法 - 图4

贪心算法 - 图5

思路：和无重叠区间一样，大差不差

代码：

package 用最少数量的箭引爆气球;

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findMinArrowShots(int[][] points) {
     //这题貌似和无重叠区间是一个道理
     //先对end进行升序
     Arrays.sort(points, new Comparator<int []>(){
      @Override
      public int compare(int[] o1, int[] o2) {
         // TODO Auto-generated method stub
         return o1[1]-o2[1];
      }

      });
        int end=points[0][1];
        //箭的数量
        int count=1;
     for(int i=1;i<points.length;i++) {
        if(end>=points[i][0]&&end<=points[i][1]) {

        }else {
           count++;
           end=points[i][1];
        }
     }
   return count;
    }
}

55. 跳跃游戏

题目描述：

贪心算法 - 图6

代码：

package 跳跃游戏1;

class Solution {
    public boolean canJump(int[] nums) {
  int n = nums.length;
    int farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        // 不断计算能跳到的最远距离
        farthest = Math.max(farthest, i + nums[i]);
        // 可能碰到了 0，卡住跳不动了
        if (farthest <= i) {
            return false;
        }
    }
   return true;
    }
}

45. 跳跃游戏 II

题目描述：

贪心算法 - 图7

思路：很明显是要穷举，既然要穷举，那么肯定是用dp啦，

代码：

package 跳跃游戏2;

class Solution {
  int[] memo;
// 主函数
public int jump(int[] nums) {
    int n = nums.length;
    // 备忘录都初始化为 n，相当于 INT_MAX
    // 因为从 0 跳到 n - 1 最多 n - 1 步
    memo = new int[n];
    Arrays.fill(memo, n);

    return dp(nums, 0);
}

// 定义：从索引 p 跳到最后一格，至少需要 dp(nums, p) 步
int dp(int[] nums, int p) {
    int n = nums.length;
    // base case
    if (p >= n - 1) {
        return 0;
    }
    // 子问题已经计算过1
    if (memo[p] != n) {
        return memo[p];
    }
    int steps = nums[p];
    // 你可以选择跳 1 步，2 步...
    for (int i = 1; i <= steps; i++) {
        // 穷举每一个选择
        // 计算每一个子问题的结果
        int subProblem = dp(nums, p + i);
        // 取其中最小的作为最终结果
        memo[p] = Math.min(memo[p], subProblem + 1);
    }
    return memo[p];
}

}

利用贪心来优化

思路：

for 循环中会陷入递归计算子问题，这是动态规划时间复杂度高的根本原因。

但是，真的需要「递归地」计算出每一个子问题的结果，然后求最值吗？直观地想一想，似乎不需要递归，只需要判断哪一个选择最具有「潜力」即可：

贪心算法 - 图8

比如上图这种情况，我们站在索引 0 的位置，可以向前跳 1，2 或 3 步，你说应该选择跳多少呢？

显然应该跳 2 步调到索引 2，因为 nums[2] 的可跳跃区域涵盖了索引区间 [3..6]，比其他的都大。如果想求最少的跳跃次数，那么往索引 2 跳必然是最优的选择。

你看，这就是贪心选择性质，我们不需要「递归地」计算出所有选择的具体结果然后比较求最值，而只需要做出那个最有「潜力」，看起来最优的选择即可。

绕过这个弯儿来，就可以写代码了：

代码：

package 跳跃游戏2之贪心优化;

class Solution {
    int jump(int[] nums) {
    int n = nums.length;
    int end = 0, farthest = 0;
    int jumps = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = Math.max(nums[i] + i, farthest);
        if (end == i) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

}

1024. 视频拼接

题目描述：

贪心算法 - 图9

贪心算法 - 图10

思路：

这很明显是个区间问题，相同起始点无疑我们肯定要选择终点最大的区间。

比较所有起点小于 clips[0][1] 的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频。

然后可以通过第二个视频区间贪心选择出第三个视频，以此类推，直到覆盖区间 [0, T]，或者无法覆盖返回 -1。

代码：

package 视频拼接;

import java.util.Arrays;

class Solution {
    public int videoStitching(int[][] clips, int T) {
        if (T == 0) return 0;
        // 按起点升序排列
        Arrays.sort(clips, (a, b) -> {  //记住这个怎么写
            return a[0] - b[0];//起点不同==>升序
        });
        // 记录选择的短视频个数
        int res = 0;

        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.length;
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个视频的区间内贪心选择下一个视频
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++;
            }
            // 找到下一个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if (curEnd >= T) {
                // 已经可以拼出区间 [0, T]
                return res;
            }
        }
        // 无法连续拼出区间 [0, T]
        return -1;
    }
}

LeetCode253 会议室

题目大致是这样的：

贪心算法 - 图11

思路：

我们首先把这些会议的时间区间进行投影：

贪心算法 - 图12

红色的点代表每个会议的开始时间点，绿色的点代表每个会议的结束时间点。

现在假想有一条带着计数器的线，在时间线上从左至右进行扫描，每遇到红色的点，计数器 count 加一，每遇到绿色的点，计数器 count 减一：

贪心算法 - 图13

这样一来，每个时刻有多少个会议在同时进行，就是计数器 count 的值，count 的最大值，就是需要申请的会议室数量。

对差分数组技巧熟悉的读者一眼就能看出来了，这个扫描线其实就是差分数组的遍历过程，所以我们说这是差分数组技巧衍生出来的解法。

代码实现

那么，如何写代码实现这个扫描的过程呢？

首先，对区间进行投影，就相当于对每个区间的起点和终点分别进行排序：

贪心算法 - 图14

代码：

package 会议室;

import java.util.Arrays;

public class Solution {
    int minMeetingRooms(int[][] meetings) {
        int n = meetings.length;
        int[] begin = new int[n];
        int[] end = new int[n];
        for(int i = 0; i < n; i++) {
            begin[i] = meetings[i][0];
            end[i] = meetings[i][1];
        }
        Arrays.sort(begin);
        Arrays.sort(end);

        // 扫描过程中的计数器
        int count = 0;
        // 双指针技巧
        int res = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (begin[i] < end[j]) {
                // 扫描到一个红点
                count++;
                i++;
            } else {
                // 扫描到一个绿点
                count--;
                j++;
            }
            // 记录扫描过程中的最大值
            res = Math.max(res, count);
        }

        return res;
    }

}

加油站

题解：

class Solution {
    int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += gas[i] - cost[i];
        }
        if (sum < 0) {
            // 总油量小于总的消耗，无解
            return -1;
        }
        // 记录油箱中的油量
        int tank = 0;
        // 记录起点
        int start = 0;
        for (int i = 0; i < n; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                // 无法从 start 走到 i
                // 所以站点 i + 1 应该是起点
                tank = 0;
                start = i + 1;
            }
        }
        return start == n ? 0 : start;
    }

}