Given an array with each element consisting of three numbers [start, end, x].
An element of array [start,end,x] means that we have to select exactly x integers from [start,end] inclusive of both start and end. Put these numbers in a Set. Do this for all elements of the array. So at the end the Set will have a size. Return the minimal possible size. Example Array= [1,3,2],[2,5,3],[5,6,2]
from 1st elements choose 2,3 from 2nd choose 2,3,5 and from 3rd choose 5,6 so the set of chosen numbers = 2,3,5,6 which has 4 elements which is the minimum. So for this input the answer or the return value is 4

My Thoughts:
I tried to think of some optimal substructure property in the hope that it will yield to a DP solution, but looks like there is no clear optimal substructure property here.

CodePudding user response：

If start and end are reasonably small number you can just calculate how many ranges element is included in then iterate thru ranges and cross numbers with biggest associated count until you cross enough of them.

public class Main {

    public static void main(String[] args) {
        int[][] arr = {{1, 3, 2}, {2, 5, 3}, {5, 6, 2}};

        Map<Integer, Ps> map = Stream.of(arr)
                .flatMap(x -> {
                    H h = new H(x[0], x[1], x[2]);
                    return IntStream.rangeClosed(x[0], x[1]).boxed().map(v -> new P(v, h));
                })
                .collect(Collectors.groupingBy(
                        P::getV,
                        Collectors.mapping(
                                P::getH,
                                Collectors.teeing(
                                        Collectors.counting(),
                                        Collectors.toList(),
                                        Ps::new))));

        Set<H> hSet = map.values().stream().flatMap(x -> x.getH().stream()).collect(Collectors.toSet());

        List<Integer> res = new ArrayList<>();
        for (H r : hSet) {
            while (r.c > 0) {
                IntStream.rangeClosed(r.s, r.e)
                        .boxed()
                        .max(Comparator.comparing(y -> map.getOrDefault(y, Ps.ZERO).getH().size()))
                        .ifPresent(v -> {
                            map.remove(v).getH().forEach(x -> x.c--);
                            res.add(v);
                        });

            }
        }
        System.out.println("res = "   res);
    }

    @AllArgsConstructor
    @Getter
    static class P {
        final int v;
        final H h;
    }

    @AllArgsConstructor
    @Getter
    static class Ps {
        public static final Ps ZERO = new Ps(0, Collections.emptyList());
        final long v;
        final List<H> h;
    }

    @AllArgsConstructor
    static class H {
        final int s, e;
        int c;
    }
}

CodePudding user response：

I think this is a DP problem. Let's define dp[i][j] as the minimum size of the set when we have selected j elements and we are at the i-th element. The answer is dp[n][k]. We can calculate dp[i][j] in O(j) time. We can iterate over j from 0 to k and for each j we can iterate over i from 0 to n-1. The time complexity is O(nk^2). I think this is the best time complexity we can get. The java code is below:

public int solve(int[][] arr, int k) {
    int n = arr.length;
    int[][] dp = new int[n][k   1];
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j <= k; j  ) {
            dp[i][j] = Integer.MAX_VALUE;
        }
    }
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j <= k; j  ) {
            if (i == 0) {
                if (j >= arr[i][2] && j <= arr[i][1] - arr[i][0]   1) {
                    dp[i][j] = arr[i][1] - arr[i][0]   1;
                }
            } else {
                for (int l = 0; l <= j; l  ) {
                    if (l >= arr[i][2] && l <= arr[i][1] - arr[i][0]   1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - l]   arr[i][1] - arr[i][0]   1);
                    }
                }
            }
        }
    }
    return dp[n - 1][k];
}