求运算后最小可能集的大小

Question

给定一个数组，每个元素由三个数字[start，end，x]组成
array[start，end，x]的元素意味着我们必须从[start、end]中精确选择x个整数，包括start和end。把这些数字放在一组里。对数组的所有元素执行此操作。因此，在最后，集合将有一个大小。返回尽可能小的大小。Example Array= [1,3,2],[2,5,3],[5,6,2]
从第1个元素中选择2，3从第2个选择2，3,5，从第3个选择5，6，因此所选数字的集合=2，3，5，6具有4个元素，这是最小的。因此，对于该输入，答案或返回值为4

我的想法：
我试图想到一些最优子结构性质，希望它能屈服于DP解，但这里似乎没有明确的最优子结构属性。

Answer 1

如果start和end是一个相当小的数字，您只需计算元素包含的范围数，然后遍历范围和具有最大关联计数的交叉数，直到您交叉了足够多的范围。

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;
}
}

Answer 2

我认为这是一个DP问题。让我们将dp[i][j]定义为当我们选择了j个元素并且我们在第i个元素时集合的最小大小。答案是dp[n][k]。我们可以在O(j(时间内计算dp[i][j]。我们可以在j上从0到k迭代，对于每个j，我们可以在i上从0迭代到n-1。时间复杂度为O(nk^2(。我认为这是我们能得到的最好的时间复杂性。java代码如下：

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];
}