Java 贪心算法解决导弹拦截问题

问题描述： 某国为了防御敌国的导弹袭击，开发出了一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以一套系统有可能不能拦截所有的导弹。

**输入：**导弹依次飞来的高度（雷达给出的高度不大于 30000 的正整数）。

**输出：**要拦截所有导弹最小需要配备多少套这种导弹拦截系统。

输入格式： n 颗依次飞来的高度 (1 <= n <= 1000)

输出格式： 要拦截所有导弹最小配备的系统数 k

示例：

输入： 5 3 5 2 6 4

输出： 2

解题思路：

这道题可以使用贪心算法来解决，每来一颗导弹，都先查找是否有能拦截它的导弹拦截系统，如果有，则直接使用该系统拦截；如果没有，则新建一个导弹拦截系统来拦截该导弹。

具体实现：

用一个 ArrayList 来存储已有的导弹拦截系统，每来一颗导弹，从后往前遍历导弹拦截系统，找到第一个能够拦截该导弹的系统，使用该系统拦截该导弹；如果找不到合适的系统，则新建一个导弹拦截系统来拦截该导弹。最后，导弹拦截系统的数量即为所需的最小系统数。

代码如下：

import java.util.ArrayList;
import java.util.Scanner;

public class MissileIntercept {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = scanner.nextInt();
        }

        ArrayList<Integer> systems = new ArrayList<>();
        int count = 0;

        for (int height : heights) {
            boolean intercepted = false;
            for (int j = systems.size() - 1; j >= 0; j--) {
                if (systems.get(j) >= height) {
                    systems.set(j, height);
                    intercepted = true;
                    break;
                }
            }
            if (!intercepted) {
                systems.add(height);
                count++;
            }
        }

        System.out.println(count);
    }
}

代码解释：

使用 Scanner 类读取输入数据。
使用 ArrayList 类存储导弹拦截系统，每个元素代表一个系统的最高拦截高度。
遍历所有导弹，对于每个导弹，从后往前遍历导弹拦截系统，找到第一个能够拦截该导弹的系统，并更新该系统的最高拦截高度。
如果找不到合适的系统，则新建一个系统，并将该导弹的高度作为该系统的最高拦截高度。
最后，输出导弹拦截系统的数量。