Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Проверка интервала времени / 25 сообщений из 30, страница 1 из 2
16.05.2018, 14:16
    #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
16.05.2018, 14:44
    #39645544
забыл ник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проверка интервала времени
ну можно разбить лист на саблисты(по хэшкоду) и уже искать пересечения только в саблистах
...
Рейтинг: 0 / 0
16.05.2018, 15:20
    #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
16.05.2018, 15:30
    #39645601
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проверка интервала времени
Tsyklop,

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

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

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

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

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

Еще предложили рекурсией.
...
Рейтинг: 0 / 0
16.05.2018, 16:06
    #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
16.05.2018, 16:12
    #39645637
Tsyklop
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проверка интервала времени
на Stackoverflow человек один скинулл ссылку . Я так посмотрел. Смысл такого алгоритма если это решается двумя циклами?
...
Рейтинг: 0 / 0
16.05.2018, 16:20
    #39645643
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проверка интервала времени
TsyklopСмысл такого алгоритма если это решается двумя циклами?
O((n+I) log n) супростив O(n 2 )
...
Рейтинг: 0 / 0
16.05.2018, 16:26
    #39645648
Tsyklop
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проверка интервала времени
BlazkowiczTsyklopСмысл такого алгоритма если это решается двумя циклами?
O((n+I) log n) супростив O(n 2 )

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


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

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

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

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

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

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

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

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

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


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