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

Учитывая массив A[ ] размера N , где каждый элемент массива представляет собой длину веревки, задача состоит в том, чтобы найти количество веревок последовательной длины, которые можно создать, соединив заданные веревки, начиная с длины 1 .

Примеры :

Input: N = 5, A[ ] = {1, 2, 7, 1, 1}

Output: 5 
Explanation: 
Length | Ropes 
    1 | [1] 
    2 | [1, 1] 
    3 | [1, 2] 
    4 | [1, 2, 1] 
    5 | [1, 2, 1, 1]

Input N = 5, A = {1, 3, 2, 4, 2} 
Output: 12 

Подход: эту проблему можно решить, используя тот факт, что если мы можем создать веревки длиной в диапазоне [1, K] и остается веревка длины L такая, что (L <= K + 1) , то мы можем создать веревки диапазона [1, K+L] , добавляя веревку длины L к каждой веревке диапазона [max(1, K-L+1), K] . Итак, чтобы решить проблему, сначала отсортируйте массив, а затем пройдитесь по массиву и каждый раз проверяйте, меньше или равен ли текущий элемент максимальной последовательной длине, которую мы получили + 1. Если найдено, что это правда, добавьте этот элемент к максимальному последовательная длина. В противном случае верните ответ.

Ниже приведена реализация вышеуказанного подхода:

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