powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Проверка интервала времени
25 сообщений из 30, страница 1 из 2
Проверка интервала времени
    #39645519
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Стало интересно. Нашел вопрос на stackoverflow.

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

Stackoverflow

Есть список интервалов, c двумя полями начало и конца. Длина списка может быть от 1 до n

Код: java
1.
List<IntervalCalendare> period



нужно проверить все периоды пересекаются они или нет. Без использования двойных циклов.

И без сторонних библиотек, например вот так :

List<Interval> intervals = new ArrayList<App.Interval>();
Код: java
1.
2.
3.
4.
5.
6.
7.
intervals.add(new Interval("23.10.2017 10:00 Z", "23.10.2017 11:00 Z"));
intervals.add(new Interval("21.10.2017 10:30 Z", "25.10.2017 11:00 Z"));
intervals.add(new Interval("23.10.2017 10:20 Z", "23.10.2017 11:00 Z"));

// все пары пересечений     
List<Intercection> intercections = Interval.getIntercection(intervals);
intercections.forEach(inter -> System.out.println(inter.toString()));
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645544
забыл ник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну можно разбить лист на саблисты(по хэшкоду) и уже искать пересечения только в саблистах
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645589
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Tsyklop,

Примерно такой код должен быть.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
    public static <E> List<E> intersection(final List<E> list1, final List<E> list2) {
        final List<E> result = new ArrayList<>();
        for (final E item : list1) {
            if (list2.contains(item)) {
                result.add(item);
            }
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    public static <E> List<E> intersection(final List<E> list, final List<E> ... lists) {
        final Stack<List<E>> stack = new Stack<List<E>>();
        stack.push(list);
        for (int index = 0; index < lists.length; index += 1) {
          stack.push(intersection(stack.peek(), lists[index]));
        }
        return stack.peek();
    }



С уважением, Валентин
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645601
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Tsyklop,

Если интервалы осортированы по стартовому времени, то можно, вроде одним циклом. Если интервалы не упорядочены, то я тоже не знаю как в один.
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645602
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Valentin KolesnikovПримерно такой код должен быть.

Только я вижу два цикла?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645620
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BlazkowiczValentin KolesnikovПримерно такой код должен быть.

Только я вижу два цикла?
нет, я тоже вижу
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645628
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Blazkowicz,

не отсортированы видать. в условии нет этого.

Вот и я вижу два цикла.

Еще предложили рекурсией.
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645632
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Valentin Kolesnikov,

Они не просто пересекаются - У каждого интервала есть время от и до.

Допустим берем интервал "21.10.2017 10:30 Z" - "25.10.2017 11:00 Z" и берем интервал "23.10.2017 10:00 Z", "23.10.2017 11:00 Z"

Если разложить то 23 число находится между 21-ым и 25-ым из первого интервала - значит они пересекаются.
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645637
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
на Stackoverflow человек один скинулл ссылку . Я так посмотрел. Смысл такого алгоритма если это решается двумя циклами?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645643
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TsyklopСмысл такого алгоритма если это решается двумя циклами?
O((n+I) log n) супростив O(n 2 )
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645648
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BlazkowiczTsyklopСмысл такого алгоритма если это решается двумя циклами?
O((n+I) log n) супростив O(n 2 )

что тут O а что n?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645652
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645783
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Эта задача решается в 1 цикл.
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645813
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЭта задача решается в 1 цикл.
Как?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645844
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как нахождение min/max.
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39645867
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, :-)


Tsyklop,
авторнужно только проверить все периоды пересекаются они или нет.

дальше ломаем мозг: "интервалы a и b пересекаются если (a.start < b.end) AND (a.end > b.start)"
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647056
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
От автора нет обратной связи. Взлетело?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647216
Tsyklop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonОт автора нет обратной связи. Взлетело?
От автора оригинальной темы?
Ссылка на stackoverflow есть выше
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647264
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonОт автора нет обратной связи. Взлетело?а что должно было взлететь? никто же решения не дал
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647278
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Оно выглядит сложным?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647290
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonОно выглядит сложным?ну я, например, даже не вижу решения за O(N), не то что без двойного цикла.
Да, есть один частный случай когда можно утверждать, что перекрытия есть Summ(Len) > (Max-Min), но он не покрывает все варианты
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647304
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
O(n) это вполне себе нормальная оценка для подобной задачи.
Автор хотел уйти от квадратичной (вложенный цикл)?
И уйдет.
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647308
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давайте вернемся в начало.

Как звучит постановка задачи?
По опыту олимпиадных задач или задач со звездочкой я могу сказать что

- их нельзя пересказывать
- они звучат кратко и предельно точно
- из них нельзя ничего выбросить
- в постановке иногда звучит подсказка на решение

Поэтому. До того как мы ринемся решать
Я еще раз спрошу автора.

Приведено оригинальное условие задачи?
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647311
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonO(n) это вполне себе нормальная оценка для подобной задачи.
Автор хотел уйти от квадратичной (вложенный цикл)?
И уйдет.я почему говорю про О(N), потому что отсутствие вложенного цикла это куда более жёсткое условие.

И действительно, в таком ракурсе её вряд ли решить, какое-то из условий автор упускает
...
Рейтинг: 0 / 0
Проверка интервала времени
    #39647314
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я решил ее одним циклом. Но я не уверен что правильно понял задачу.

Вернее сказать я ее видоизменил и решил.

Я так часто делаю. Approach такой.
...
Рейтинг: 0 / 0
25 сообщений из 30, страница 1 из 2
Форумы / Java [игнор отключен] [закрыт для гостей] / Проверка интервала времени
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]