
Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
16.05.2018, 14:16
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
Стало интересно. Нашел вопрос на stackoverflow. Как сделать двойным циклом в принципе понятно, а вот без него как? у меня чет идей нет. Подскажете может? Stackoverflow Есть список интервалов, c двумя полями начало и конца. Длина списка может быть от 1 до n Код: java 1. нужно проверить все периоды пересекаются они или нет. Без использования двойных циклов. И без сторонних библиотек, например вот так : List<Interval> intervals = new ArrayList<App.Interval>(); Код: java 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 14:44
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
ну можно разбить лист на саблисты(по хэшкоду) и уже искать пересечения только в саблистах ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 15:20
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
Tsyklop, Примерно такой код должен быть. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. С уважением, Валентин ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 15:30
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
Tsyklop, Если интервалы осортированы по стартовому времени, то можно, вроде одним циклом. Если интервалы не упорядочены, то я тоже не знаю как в один. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 15:31
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
Valentin KolesnikovПримерно такой код должен быть. Только я вижу два цикла? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 15:53
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
BlazkowiczValentin KolesnikovПримерно такой код должен быть. Только я вижу два цикла? нет, я тоже вижу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 16:02
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
Blazkowicz, не отсортированы видать. в условии нет этого. Вот и я вижу два цикла. Еще предложили рекурсией. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 16:06
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
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.05.2018, 16:12
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
на Stackoverflow человек один скинулл ссылку . Я так посмотрел. Смысл такого алгоритма если это решается двумя циклами? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 16:20
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
TsyklopСмысл такого алгоритма если это решается двумя циклами? O((n+I) log n) супростив O(n 2 ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 16:26
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
BlazkowiczTsyklopСмысл такого алгоритма если это решается двумя циклами? O((n+I) log n) супростив O(n 2 ) что тут O а что n? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 16:30
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
https://ru.wikipedia.org/wiki/Вычислительная_сложность Чему вас там учат только... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
16.05.2018, 20:58
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
Эта задача решается в 1 цикл. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
17.05.2018, 00:00
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
maytonЭта задача решается в 1 цикл. Как? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
17.05.2018, 07:25
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
Как нахождение min/max. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
17.05.2018, 08:45
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
mayton, :-) Tsyklop, авторнужно только проверить все периоды пересекаются они или нет. дальше ломаем мозг: "интервалы a и b пересекаются если (a.start < b.end) AND (a.end > b.start)" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
19.05.2018, 15:39
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
От автора нет обратной связи. Взлетело? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 12:15
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
maytonОт автора нет обратной связи. Взлетело? От автора оригинальной темы? Ссылка на stackoverflow есть выше ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 16:29
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
maytonОт автора нет обратной связи. Взлетело?а что должно было взлететь? никто же решения не дал ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 18:06
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
Оно выглядит сложным? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 19:15
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
maytonОно выглядит сложным?ну я, например, даже не вижу решения за O(N), не то что без двойного цикла. Да, есть один частный случай когда можно утверждать, что перекрытия есть Summ(Len) > (Max-Min), но он не покрывает все варианты ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 20:44
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
O(n) это вполне себе нормальная оценка для подобной задачи. Автор хотел уйти от квадратичной (вложенный цикл)? И уйдет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 21:21
|
|||
|---|---|---|---|
Проверка интервала времени |
|||
|
#18+
Давайте вернемся в начало. Как звучит постановка задачи? По опыту олимпиадных задач или задач со звездочкой я могу сказать что - их нельзя пересказывать - они звучат кратко и предельно точно - из них нельзя ничего выбросить - в постановке иногда звучит подсказка на решение Поэтому. До того как мы ринемся решать Я еще раз спрошу автора. Приведено оригинальное условие задачи? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.05.2018, 21:38
|
|||
|---|---|---|---|
|
|||
Проверка интервала времени |
|||
|
#18+
maytonO(n) это вполне себе нормальная оценка для подобной задачи. Автор хотел уйти от квадратичной (вложенный цикл)? И уйдет.я почему говорю про О(N), потому что отсутствие вложенного цикла это куда более жёсткое условие. И действительно, в таком ракурсе её вряд ли решить, какое-то из условий автор упускает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|

start [/forum/topic.php?fid=59&mobile=1&tid=2122040]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
172ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
57ms |
get tp. blocked users: |
2ms |
| others: | 236ms |
| total: | 508ms |

| 0 / 0 |

Извините, этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
... ля, ля, ля ...