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

start [/forum/topic.php?fid=59&fpage=46&tid=2122040]: |
0ms |
get settings: |
11ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
57ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
58ms |
get tp. blocked users: |
2ms |
| others: | 14ms |
| total: | 178ms |

| 0 / 0 |

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