Блог

Главная - Вопросы по программированию - Структура данных для проверки перекрытия нескольких периодов

Структура данных для проверки перекрытия нескольких периодов

#java #algorithm

Вопрос:

У меня есть класс Period , который представлен start и end датами, где end после start . Мне нужно написать функцию, чтобы проверить, перекрываются ли периоды.

Простой подход состоит в том, чтобы сверять каждый период с каждым другим периодом. Есть ли способ представить структуру данных, которая будет работать быстрее?

 class Period {
      LocalDateTime start;
      LocalDateTime end;
}
 

boolean isOverlap(Set<Period> periods) {
    // TODO put the code here
}

isOverlap должен вернуться true , когда по крайней мере два периода перекрываются.

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

1. Не могли бы вы уточнить, когда isOverlap следует вернуть значение true? Должно ли это происходить, когда все периоды перекрывают все остальные периоды?

2. Я бы реализовал Comparable интерфейс. Затем с a TreeSet вы можете сравнить по порядку.

3. @Гобой Точно, как бы вы реализовали compareTo пару свиданий или пару моментов? Является ли Хэллоуин к Рождеству больше или меньше, чем с 1 по 20 ноября?

4. @Basil Bourque Это зависит от того, чего вы хотите достичь. Для этого конкретного случая я бы реализовал его так же, как Stream сортируется в принятом ответе.

Ответ №1:

Проверка каждого периода по сравнению с каждым другим периодом будет иметь временную сложность O(n 2). Вместо этого я бы отсортировал их по времени начала и окончания, а затем повторил бы список. Таким образом, период может перекрывать только периоды непосредственно до и после него (или несколько последующих периодов до или после него — но это несущественно, так как вы ищете единственное перекрытие для возврата true ). Вы можете просмотреть список и проверить это. Общая стоимость этого алгоритма будет равна стоимости сортировки, O(nlog(n)):

 boolean isOverlap(Set<Period> periods) {
    List<Period> sorted =
        periods.stream()
               .sorted(Comparator.comparing((Period p) -> p.start)
                                 .thenComparing(p -> p.end))
               .collect(Collectors.toList());
    for (int i = 0; i < sorted.size() - 1;   i) {
        if (sorted.get(i).end.compareTo(sorted.get(i   1).start) > 0) {
            return true;
        }
    }
    return false;
}

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

1. Я думаю, что это должно быть » > 0`, чтобы это сработало.

2. @yu.pitomets arg, да, это верно. Там был кратковременный провал в концентрации, извините за это. Спасибо, что заметили! Отредактировано и исправлено.

Метки: