Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 28.12.2017
Сообщений: 22

Перекрытие временных промежутков

31.08.2018, 11:18. Показов 1319. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Решаю задачку, где дан список содержащий время (в милисекундах) прихода и ухода посетителя.
Например: (время перевожу в удобоваримое) IN 08:45 Out 09:00, 08:47 -09:13
Получается максимум 2 человека в период с 08:47 до 09:00
Я составил алгоритм, который как мне кажется решает задачку правильно и проходит несколько тестов, но думаю, что можно снизить сложность алгоритма.
Основной метод:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public List<Info> max(List<Visit> visits) {
        List<Info> periods = new ArrayList<>();
        List<Info> allPeriods = new ArrayList<>();
        Map<Long, List<Info>> map = new HashMap<>();
        int maxSize = 0;
        long hash = 0;
        for (int i = 0; i < visits.size(); i++) {
            long count = 1;
            for (int j = i; j < visits.size(); j++) {
                if (visits.get(i).out >= visits.get(j).in) {
                    allPeriods.add(new Info(count, visits.get(j).in, visits.get(j).out));
                    count++;
                }
            }
            if (allPeriods.size() >= maxSize) {
                maxSize = allPeriods.size();
                hash = visits.get(i).in;
                map.put(visits.get(i).in, new ArrayList<>(allPeriods));
            }
            allPeriods.clear();
        }
        allPeriods = map.get(hash);
        for (int k = 1, m = 0; k < allPeriods.size(); k++) {
            long start = Math.max(allPeriods.get(m).start, allPeriods.get(k).start);
            long finish = Math.min(allPeriods.get(m).end, allPeriods.get(k).end);
            allPeriods.set(0, new Info(allPeriods.size(), start, finish));
        }
        periods.add(allPeriods.get(0));
        return periods;
    }
Текущая сложность (по моему мнению) квадратичная, т.к. присутствует двойной цикл и сортировка. Хотелось бы снизить до линейной. Подскажите как можно этого добиться.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
31.08.2018, 11:18
Ответы с готовыми решениями:

Алгоритм временных промежутков
Здравствуйте! Помогите пожалуйста написать алгоритм, я сам уже голову сломал как это сделать просто и эффективно. Значит условия такие....

Как построить генератор временных промежутков?
Имеется литературный текст, например, на английском. Нужно вводить в программу слова текста через равные промежутки времени, (например, 0,1...

Запись временных промежутков в массив и сортировка их по возрастанию
procedure swap(x, y: integer); var t: integer; begin t := x; x := y; y := t end; const

3
Автоматизируй это!
Эксперт Python
 Аватар для Welemir1
7392 / 4819 / 1246
Регистрация: 30.03.2015
Сообщений: 13,694
Записей в блоге: 29
31.08.2018, 11:54
Цитата Сообщение от digital-dd Посмотреть сообщение
Решаю задачку, где дан список содержащий время (в милисекундах) прихода и ухода посетителя.
И? что с ним делать, что ищем? полную задачу огласите пожалуйста
0
0 / 0 / 0
Регистрация: 28.12.2017
Сообщений: 22
31.08.2018, 12:02  [ТС]
Да, вероятно я не дописал условие. Необходимо найти временной промежуток с максимальным количеством посетителей.
0
 Аватар для Aviz__
2755 / 2062 / 509
Регистрация: 17.02.2014
Сообщений: 9,491
31.08.2018, 13:51
так не?
У каждого объекта визитер есть время прихода. Проходясь 1 раз по визитерам, ты создаешь, на определенных границах времени, минимум два, объекта ПлотностьВизитеров(кодичествоВизитеров). Далее, на этих самых временных границах, когда их перешагиваешь, сравниваешь ПлотностьВизитеров последний и предпоследний на максимум.
В теории, линейка видеться)).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
31.08.2018, 13:51
Помогаю со студенческими работами здесь

Составить программу, в которой вводятся значения двух временных промежутков в часах
Z=(√m−√n)/ m Текст: Составить программу, в которой вводятся значения двух временных промежутков в часах. Разницу между этими промежутками в...

Написать программу, в которой вводятся значения двух временных промежутков в часах
Помогите написать программу, в которой вводятся значения двух временных промежутков в часах. Разницу между этими промежутками в минутах и...

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

Проверка промежутков
Добрый вечер. Помогите с реализацией вот такой вещи. Я ввожу первое число. Это будет первое расстояние в промежутках. Допустим,...

Определение промежутков в массиве
Доброго дня, весь день ломаю голову и никак не могу решить возникшую перед самим собой задачу. Имеется у меня в наличие массив...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru