Dynami c Программирование на интервалах

Question

Вам задан массив непрерывных интервалов, т. Е. { [a,b],[b,c],[c,d],...,[g,h],[h,i] } Учитывая запрос типа n m k, нам нужно вывести количество интервалов между n,m (inclusive, 1-based indexing), содержащее k.

Мой подход: (Наивно проверять все интервалы между n,m и вести счетчик .)

Это работает, если m-n и количество запросов мало, но это будет действительно неэффективно для больших значений n,m и нескольких запросов.

Так что я подумал о Dynami c Подход к программированию так, что мы можем сохранить количество интервалов, содержащих z, до интервала с номером, скажем x в массиве dp[x][z], тогда я могу ответить на любой запрос n m k как dp[m][k]-dp[n][k]. Но это также дает сбой, если интервалы, указанные в массиве, слишком велики, поскольку для создания массива dp потребуется больше времени.

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

Любые подсказки будут полезны.

Пример:

Массив: { [1,3],[3,2],[2,1],[1,5],[5,3] }

Запросы: { 1 2 2 }, { 1 3 3 }, { 2 2 4 }

Выход: { 2 }, { 2 }, { 0 }

Answer 1

Я бы решил эту проблему следующим образом.

Сначала я бы представил другой массив структуры данных в форме:

[(ai,bi,ci)]

, где

ai - interval start
bi - interval end
ci - count of intervals of original sequence hitting interval [ai,bi]

ai < bi
a(i+1) = bi

поэтому эта новая структура данных охватывает весь диапазон исходной структуры, она увеличивается и имеет желаемое количество исходных интервалов.

Теперь, чтобы найти число, нам нужно только k и выполнить некоторый бинарный поиск, чтобы найти интервал.