Найдите двоичную строку N-длины, имеющую максимальную сумму элементов из заданных диапазонов

Дан массив пар ranges[] размера M и целое число N , задача состоит в том, чтобы найти двоичную строку длины N такую, чтобы сумма элементов строки из заданных диапазонов была максимально возможной.

Примеры:

Input: N = 5, M = 3, ranges[] = {{1, 3}, {2, 4}, {2, 5}}
Output: 01100
Explanation:
Range [1, 3]: Freq of 0’s = 1, Freq of 1’s = 2. Sum = 1*2 = 2
Range [2, 4]: Freq of 0’s = 1, Freq of 1’s = 2. Sum = 1*2 = 2
Range [2, 5]: Freq of 0’s = 2, Freq of 1’s = 2. Sum = 2*2 = 4
Therefore, the required sum = 2 + 2 + 4 = 8, which is the maximum possible.

Input: N = 6, M = 1, ranges = {{1, 6}}
Output: 000111

Подход: Данную проблему можно решить, найдя абсолютную разницу между количеством нулей и количеством единиц как можно меньше для каждого диапазона. Таким образом, идея состоит в том, чтобы разместить в строке как 0 , так и 1 почти с одинаковой частотой. Лучший способ сделать это — попеременно расположить 0 и 1 .

Следовательно, из приведенных выше наблюдений, чтобы сгенерировать результирующую строку, идея состоит в том, чтобы перебрать диапазон [1, N] с использованием переменной i , и если значение i нечетное, то напечатать 0, иначе напечатать 1 .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)