Как стать автором
Обновить

Комментарии 1

Неплохо в теории, но есть вероятность выделить очень много памяти под большой массив, хотя большая ее часть не будет использована.
Например:
Входные данные:
— въезды = [1, 3, 5]
— выезды = [2, 10000, 10]
— k = 1
В данном случае будет выделен массив из 10 тысяч целых чисел.

Исходя из условия задачи, у нас не может быть в любом из этих массивов числа больше 365 (366 в високосный год). И то это я еще на целый год «сезон» растянул. Так что потери памяти будут не большими.
Причем при правильно написанной логике выход из считающего метода будет выполнен после первого же дня, в который число гостей превысит число комнат, и вся память из-под массива станет доступна сборщику мусора.
Так что первое решение не такое уж и плохое.
НО!
а зачем вообще выделять память под этот массив?
   private static boolean checkRooms(List<Integer> arrivals, List<Integer> departures, int totalRooms) {
        int maxDate= maxOf(arrivals, departures);
        int busyRooms = 0;

        for (int i = 1; i <= maxDate; i++) {
            if (arrivals.contains(i)) {
                busyRooms++;
            }
            if (departures.contains(i)) {
                busyRooms--;
            }
            if (busyRooms > totalRooms) {
                return false;
            }
        }
        return true;
    }


Вдогонку: на самом деле максимальную дату нужно искать не в обоих массивах, а только в массиве прибытий. В данном примере после 5го дня количество занятых комнат расти точно не будет, поэтому можно дальше и не считать. (Эта же поправка позволяет прилично уменьшить размер массива, если очень хочется его все-таки использовать).
В моем методе нужно инициализировать значение maxDate вот так:
int maxDate = Collections.max(arrivals);
и все будет работать корректно. Я специально пишу это ниже примера с кодом, чтобы показать ход рассуждений и постепенную оптимизацию первого решения автора. Ведь это же учебная статья :-)
Зарегистрируйтесь на Хабре , чтобы оставить комментарий