Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
Стало интересно. Нашел вопрос на stackoverflow.

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

Stackoverflow

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

List<IntervalCalendare> period


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

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

List<Interval> intervals = new ArrayList<App.Interval>();
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()));
16 май 18, 14:16    [21413515]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
забыл ник
Member

Откуда:
Сообщений: 2517
ну можно разбить лист на саблисты(по хэшкоду) и уже искать пересечения только в саблистах
16 май 18, 14:44    [21413648]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Valentin Kolesnikov
Member

Откуда:
Сообщений: 3064
Tsyklop,

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

    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();
    }


С уважением, Валентин
16 май 18, 15:20    [21413887]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Blazkowicz
Member

Откуда:
Сообщений: 24443
Tsyklop,

Если интервалы осортированы по стартовому времени, то можно, вроде одним циклом. Если интервалы не упорядочены, то я тоже не знаю как в один.
16 май 18, 15:30    [21413941]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Blazkowicz
Member

Откуда:
Сообщений: 24443
Valentin Kolesnikov
Примерно такой код должен быть.

Только я вижу два цикла?
16 май 18, 15:31    [21413945]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7129
Blazkowicz
Valentin Kolesnikov
Примерно такой код должен быть.

Только я вижу два цикла?

нет, я тоже вижу
16 май 18, 15:53    [21414085]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
Blazkowicz,

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

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

Еще предложили рекурсией.
16 май 18, 16:02    [21414142]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
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-ым из первого интервала - значит они пересекаются.
16 май 18, 16:06    [21414156]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
на Stackoverflow человек один скинулл ссылку. Я так посмотрел. Смысл такого алгоритма если это решается двумя циклами?
16 май 18, 16:12    [21414172]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Blazkowicz
Member

Откуда:
Сообщений: 24443
Tsyklop
Смысл такого алгоритма если это решается двумя циклами?

O((n+I) log n) супростив O(n2)
16 май 18, 16:20    [21414196]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
Blazkowicz
Tsyklop
Смысл такого алгоритма если это решается двумя циклами?

O((n+I) log n) супростив O(n2)


что тут O а что n?
16 май 18, 16:26    [21414221]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Blazkowicz
Member

Откуда:
Сообщений: 24443
https://ru.wikipedia.org/wiki/Вычислительная_сложность
Чему вас там учат только...
16 май 18, 16:30    [21414235]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
Эта задача решается в 1 цикл.
16 май 18, 20:58    [21414868]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
mayton
Эта задача решается в 1 цикл.

Как?
17 май 18, 00:00    [21415130]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
Как нахождение min/max.
17 май 18, 07:25    [21415539]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3312
mayton, :-)


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


дальше ломаем мозг: "интервалы a и b пересекаются если (a.start < b.end) AND (a.end > b.start)"
17 май 18, 08:45    [21415637]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
От автора нет обратной связи. Взлетело?
19 май 18, 15:39    [21422472]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
Tsyklop
Member

Откуда: Украина
Сообщений: 637
mayton
От автора нет обратной связи. Взлетело?

От автора оригинальной темы?
Ссылка на stackoverflow есть выше
20 май 18, 12:15    [21423487]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3312
mayton
От автора нет обратной связи. Взлетело?
а что должно было взлететь? никто же решения не дал
20 май 18, 16:29    [21423781]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
Оно выглядит сложным?
20 май 18, 18:06    [21423924]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3312
mayton
Оно выглядит сложным?
ну я, например, даже не вижу решения за O(N), не то что без двойного цикла.
Да, есть один частный случай когда можно утверждать, что перекрытия есть Summ(Len) > (Max-Min), но он не покрывает все варианты
20 май 18, 19:15    [21423990]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
O(n) это вполне себе нормальная оценка для подобной задачи.
Автор хотел уйти от квадратичной (вложенный цикл)?
И уйдет.
20 май 18, 20:44    [21424102]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
Давайте вернемся в начало.

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

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

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

Приведено оригинальное условие задачи?
20 май 18, 21:21    [21424162]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3312
mayton
O(n) это вполне себе нормальная оценка для подобной задачи.
Автор хотел уйти от квадратичной (вложенный цикл)?
И уйдет.
я почему говорю про О(N), потому что отсутствие вложенного цикла это куда более жёсткое условие.

И действительно, в таком ракурсе её вряд ли решить, какое-то из условий автор упускает
20 май 18, 21:38    [21424201]     Ответить | Цитировать Сообщить модератору
 Re: Проверка интервала времени  [new]
mayton
Member

Откуда: loopback
Сообщений: 37864
Я решил ее одним циклом. Но я не уверен что правильно понял задачу.

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

Я так часто делаю. Approach такой.
20 май 18, 22:06    [21424251]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Java Ответить