二分算法-种树

题目描述

云服务平台新上线一个绿化规划服务 , 园林部门用其帮助规划种树任务 : 在某个笔直的路段栽种 num 棵树
假定该路段规划设计图上的坐标自 0 开始 , 二维数组 areas 按照坐标升序以 [起点坐标，终点坐标] 记录了规划绿化区间 , 且区间互不相
交 。树木只能栽种在绿化区间内 , 且在不同的整数坐标位置上。

尽量稀疏种植 , 每种种植方案中相邻两棵树的间距最小的记 为 minDistance , 其中 minDistance最大的则为最佳种植方案 , 请返回minDistance最大可能是多少。若无法在 areas 给出的规划绿化区间内完成种树任务 , 请返回 -1

示例1:
输入: num = 5, aress = [[1,3] [5,6] [8,9], [10,11]]
输出 : 2
解释 : 起点坐标为0, 终点坐标为 11 ( 最后一个区间的终点坐标 ) , 合计12个坐标点。 最佳种植方案有 : [1,3,5,8,10] [1,3,5,8,11]
[1,3,5,9,11] [1,3,6,8,10] [1,3,6,8,11] [1,3,6,9,11], 最小间距的最大值为2。

示例2:
输入: num = 5, aress = [[1,3] [5,5]]
输出 : -1
解释 : 区间[1,3] [5,5]内无法种植5棵树。

提示 :
1 < areas.length < 200
2 <= num <= 1000
0 <= areas[i][0] <= areas[i][1] <= 10^7

/**

• @param num 种树的数量
• @param areas 种树区间
• @return 最大距离
  */
  public int distanceBetweenTree(int num, int[][] areas) {

};

public class DistanceBetweenTree {
    public static void main(String[] args) {
        int[][][] areas = new int[][][]{
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 6}, {8, 9}, {10, 11}},
                {{1, 3}, {5, 5}},
                {{1, 3}, {5, 5}},
                {{1, 3}, {5, 5}},
                {{1, 3}, {5, 5}},
                {{1, 3}, {5, 5}},
        };
        int[] num = new int[]{
                11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1
        };
        for (int i = 0; i < areas.length; i++) {
            int res = distanceBetweenTree(num[i], areas[i]);
            System.out.printf("areas=%s,num=%s,res=%s \n\n", Arrays.deepToString(areas[i]), num[i], res);
        }
    }

    /**
     * @param num   种树的数量
     * @param areas 种树区间
     * @return 最大距离
     */
    public static int distanceBetweenTree(int num, int[][] areas) {
        //将二维数组表现为一维数组，方便后继种树判断，并且在左右增一个数据作为边界，方便直接处理areas,
        //将treeArr数组中能种树的位置设置为1，其他的默认设置为0
        int[] treeArr = new int[areas[areas.length - 1][1] + 2];
        int sum = 0;
        for (int[] area : areas) {
            for (int i = area[0]; i <= area[1]; i++) {
                treeArr[i] = 1;
                sum++;
            }
        }
        if (sum < num) {
            return -1;
        }

        System.out.println(Arrays.toString(treeArr));
        return binarySearch(num, treeArr, areas);
    }

    public static int binarySearch(int num, int[] treeArr, int[][] areas) {
        int res = -1;
        int left = 1;
        int right = areas[areas.length - 1][1];
        while (left <= right) {
            int mid = left + (right - left) / 2;
            boolean check = checkDistance(num, mid, treeArr, areas[0][0]);
            if (check) {
                left = mid + 1;
                res = mid; //在mid满足可以种树的情况下进行赋值
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    private static boolean checkDistance(int num, int mid, int[] treeArr, int startIndex) {
        int[] treeArr2 = Arrays.copyOf(treeArr, treeArr.length); //treeArr2为打印效果，实际是不需要的，若不打印直接替换成treeArr
        int countTree = 1;
        treeArr2[startIndex] = 2;
        int preIndex = startIndex;
        for (int i = startIndex + 1; i < treeArr2.length; i++) {
            if (treeArr2[i] == 0) { //无法种树，直接跳过
                continue;
            }
            if ((i - preIndex) >= mid && treeArr2[i] == 1) { //间距符合mid，并且是可以种树情况下，种树
                preIndex = i;
                countTree++;
                treeArr2[i] = 2;
            }
            if (countTree >= num) { //当需要种的数量大于等于num时，则说明mid距离的间隔可以实现种树，种树的策略都可以打印出来
                System.out.printf(">> T mid=%s,tree2=%s \n", mid, Arrays.toString(treeArr2));
                return true;
            }
        }
        System.out.printf("F mid=%s,tree2=%s \n", mid, Arrays.toString(treeArr2));
        return false;
    }
}

本文地址：https://blog.csdn.net/weixin_46875212/article/details/112852335