Определите самый длинный сегмент целых чисел в пределах включающего диапазона, который не содержит неправильного числа, используя Java 8

Question

Учитывая массив неверных чисел и диапазон целых чисел, как я могу определить самый длинный сегмент целых чисел в этом включающем диапазоне, который не содержит плохого числа?

Например, вам дается нижний предел l = 3 и верхний предел r = 48, Массив badNumbers = [37,7,22,15,49,60]. Сегменты без плохих номеров: [3,6], [8,14], [16,21], [23,36] и [38,48]. Самый длинный сегмент - [23,36] и состоит из 14 элементов.

Проблема: Описание функции Завершите функцию goodStatement в редакторе ниже. Функция должна возвращать целое число, обозначающее длину самого длинного непрерывного диапазона натуральных чисел в диапазоне от l до r включительно, который не включает плохих чисел.

goodSegment имеет следующие параметры: badNumbers [badNumbers [0], ... badNumbers [n-1]]: массив целых чисел l: целое число, нижняя граница, включая r: целое число, верхняя граница, включительно

Ограничения 1 ≤ n ≤10 ^ 5 1 ≤ badNumbers [i] ≤ 10 ^ 9 badNumbers содержит отдельные элементы

Я пытался вот так

private boolean withinRange (int [] array, int lower, int upper) {
    int start = 0;
    int end = array.length;
    while (start < end) {
        int current = (start + end) / 2;
        if (array[current] >= upper) {
            end = current;
        } else if (array[current] < lower) {
            start = current + 1;
        } else {
            return true;
        }
    }
    return false;
}

Пример

Answer 1

Go по неверным числам в возрастающем порядке, вычисляя длину левого сегмента. Для верха эти расчеты могут потребоваться отдельно. Даже если верхнее число является неправильным, вычисления левого сегмента logi c все равно останутся;

3 --------------------- 48
   7   15  22   37         49     60
|4 | 7 | 6 | 14 |  10   |

На диаграмме выше показан расчет сегмента на картинке. Ниже приведен код того же:

private static int getLongestSegment(int[] badNumbers, int lower, int upper) {
        int longestSegment = 0;
        int currentSegment = 0;
        int lastGoodNumber = lower;

        // Sort bad numbers
        Arrays.sort(badNumbers);

        // Traverse over bad numbers, exploring left segment till all numbers are covered or upper is exceeded
        for (int i = 0; i < badNumbers.length && badNumbers[i] <= upper; i++) {
            currentSegment = badNumbers[i] - lastGoodNumber;
            if (currentSegment > longestSegment) {
                longestSegment = currentSegment;
            }

            lastGoodNumber = badNumbers[i] + 1;
        }

        // Handle left segment of upper
        currentSegment = upper - lastGoodNumber + 1;
        if (currentSegment > longestSegment) {
            longestSegment = currentSegment;
        }

        return longestSegment;
    }

Answer 2

Если можно, я внесу два небольших изменения в ответ Ришаба:

Преобразование массива с последующей сортировкой:

    int[] arr = badNumbers.stream().mapToInt(i->i).toArray();
    // Sort bad numbers
    Arrays.sort(arr);

Приведенный ниже ответ даст точный ответ вместо lastGoodNumber = badNumbers [i] + 1;

     if (arr[i]>=l) {lastGoodNumber = arr[i] + 1;
        }