算法-贪心算法

柔光的暖阳◎ 2024-03-24 21:14 142阅读 0赞

1、分糖果问题

public int candy (int[] arr) {
        int n = arr.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                nums[i] = nums[i - 1] + 1;
            }
        }
        int res = nums[n - 1];
        for (int i = n - 1; i >= 1; i--) {
            if (arr[i - 1] > arr[i] && nums[i-1] <= nums[i]) {
                nums[i - 1] = nums[i] + 1;
            }
            res += nums[i - 1];
        }
        return res;
    }

2、主持人调度

public int minmumNumberOfHost (int n, int[][] startEnd) {
        int res = 0;
        int length = startEnd.length;
        int[] start = new int[length];
        int[] end = new int[length];
        for (int i = 0; i < startEnd.length; i++) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        Arrays.sort(start, 0, length);
        Arrays.sort(end, 0, length);
        int j = 0;
        for (int i = 0; i < length; i++) {
            if (start[i] >= end[j]) {
                j++;
            } else {
                res ++;
            }
        }
        return res;
    }