Длина минимальной подпоследовательности, которая охватывает всю длину массива?

Question

Мне дан целочисленный массив длины N, с элементами, представляющими промежутки, которые он может охватывать от 0 до N-1. поэтому для элемента a [i] элемент охватывает диапазон от max (i-a [i], 0) до min (i + a [i], N-1).

Как найти длину наименьшей подпоследовательности, которая охватывает все пространство , т. Е. От 0 до N-1;

Пример: для этого массива [1,1,1,3,2,1,1,4] ответ должен быть 2

Это то, что у меня так далеко, это работает не во всех случаях

int arr[] = {2,2,1,3,2,1,1,4,1,1,1,1,1,1,1,1,1,1}; // Fails for this case
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int[] sortedIndices = IntStream.range(0, arr.length)
                .boxed().sorted((i, j) -> span(arr[j],j,arr.length) - span(arr[i],i,arr.length))
                .mapToInt(ele -> ele).toArray();

        int i=0;
        int ans = 0;
        while (min>0 || max<arr.length-1) {
            int ind = sortedIndices[i++];
            int val = arr[ind];

            int tmin = Math.max(0,ind-val);
            int tmax = Math.min(arr.length - 1, ind+val);
            if(tmin < min || tmax > max)
                ans++;

            min = Math.min(min, tmin);
            max = Math.max(max, tmax);
        }

        System.out.println(ans);

Answer 1

Кажется, что проблема может быть решена простым жадным алгоритмом.

Для каждой записи массива создайте интервал с полями start и finish (a[i].start = i-arr[i] etc)

Сортировка интервалов по полю начала.

Найдите интервал с самым правым finish среди тех, которые охватывают 0, сделайте maxx=a[i].finish.

Сканируйте интервалы с start в 0..maxx диапазоне, выберите один с самым правым finish.

Продолжить.

Быстрая реализация Python (возможно, потребуется еще несколько проверок)

ar = [2,2,1,3,2,1,4,4]
n = len(ar)
a = [(max(0, i-ar[i]), min(i+ar[i], n-1)) for i in range(n)]
print(ar)
a.sort()
print(a)
cnt = 0
maxx = -1
left = 0
i = 0
while i < n and maxx < n - 1:
    while i < n and a[i][0] <= left and maxx < n - 1:
        maxx = max(a[i][1], maxx)
        i+=1
    print("maxx ", maxx)
    left = maxx
    cnt += 1

print("cover ", cnt)

[2, 2, 1, 3, 2, 1, 4, 4]
[(0, 2), (0, 3), (0, 6), (1, 3), (2, 6), (2, 7), (3, 7), (4, 6)]
maxx  6
maxx  7
cover  2