Форум Академгородка, Новосибирск > Задачка на подсчет времени
Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Задачка на подсчет времени
Форум Академгородка, Новосибирск > Компьютеры и сети > Программирование
stellarium
Есть ряд записей, в которых фигурирует время. Начало интервала и конец интервала.
Сразу для примера три записи:
10 00 - 13 30, 12 00 - 14 00, 15 00 - 17 00.
Грубо говоря, можно сравнить с подсчетом рабочего времени сотрудника, минус перерывы и минус наложения интервалов, когда сотрудник занимался сразу несколькими делами одновременно...
Требуется решение, как подсчитать суммарное время с вычетом дыр в интервалах и вычетом наложения интервалов друг на друга. В общем виде, чтобы работало с любым количеством записей и любыми временами. В идеале в MYSQl, но пойдет и просто сам алгоритм
В рассматриваемом выше случае получается 6 часов (с вычетом часа 14 00 - 15 00).
Eyeless Watcher
Я бы считал не проработанное время, а время простоя.
Сортируем отрезки по времени начала по возрастанию (и заодно убеждаемся, что для каждого отрезка начало не позже конца) и идем по ним, запоминая самый правый конец отрезка из рассмотренных. Как только начало очередного отрезка правее этого запомненного конца - у нас разрыв, прибавляем ко времени простоя его длину.
В конце вычитаем из полной длины интервала (максимум из концов минус минимум из начал) время простоя.
stellarium
Цитата(Eyeless Watcher @ 07.06.2012, 18:11) *
Я бы считал не проработанное время, а время простоя.
Сортируем отрезки по времени начала по возрастанию (и заодно убеждаемся, что для каждого отрезка начало не позже конца) и идем по ним, запоминая самый правый конец отрезка из рассмотренных. Как только начало очередного отрезка правее этого запомненного конца - у нас разрыв, прибавляем ко времени простоя его длину.
В конце вычитаем из полной длины интервала (максимум из концов минус минимум из начал) время простоя.

Три интервала для примера:
10 00 - 16 00.
12 00 - 12 30.
13 30 - 17 00
Отсортированы по возрастанию начал интервалов (сверху вниз). Ваш алгоритм посчитает разницу между интервалами 12 30 и 13 30 как пустоту и прибавит ее ко времени простоя и тем самым допустит ошибку, так как этот интервал учтен в интервале 10 00 - 16 00.
Eyeless Watcher
Перечитайте алгоритм, что ли. 16:00 будет объявлен самым правым концом на первом шаге и проживет в этом звании до последнего.
stellarium
Цитата(Eyeless Watcher @ 07.06.2012, 18:27) *
Перечитайте алгоритм, что ли. 16:00 будет объявлен самым правым концом на первом шаге и проживет в этом звании до последнего шага.

А, да, верно, если проходить каждый раз по циклу по всем отрезкам отрезка правее этого запомненного конца тогда все ок.
Eyeless Watcher
Цитата(stellarium @ 07.06.2012, 19:30) *
Цитата(Eyeless Watcher @ 07.06.2012, 18:27) *
Перечитайте алгоритм, что ли. 16:00 будет объявлен самым правым концом на первом шаге и проживет в этом звании до последнего шага.

А, да, верно, если проходить каждый раз по циклу по всем отрезкам отрезка правее этого запомненного конца тогда все ок.

У вас там программист есть? Дайте ему прочитать, вас куда-то откровенно уносит. Нету там вложенного цикла, для того изначальная сортировка и проводилась.
На пальцах:
Нажмите для просмотра прикрепленного файла
Черное - то, что уже учтено, синяя линия - запомненный самый правый конец. Красное - очередной отрезок. В силу сортировки вариантов расположения у него три.
В первом случае (конец нового отрезка левее синей линии) мы ничего не трогаем и идем дальше.
Во втором (начало до, конец - после) сдвигаем синюю линию на правую границу красного отрезка.
В третьем (начало после) добавляем к простою разницу между синей линией и началом нового отрезка и так же сдвигаем синюю линию.
Смыть, повторить.
MBo
Отсортировать по времени набор записей (время, +1 как признак начала или -1 для конца интервала). При равных временах начало раньше конца (чтобы не было нулевых разрывов)
А = 0
Далее просто идем по набору, прибавляя к A второе поле. Переход A из нуля в 1 - запоминаем начало работы, переход в ноль - конец, вычисляем разность.
dreamflyer
есть массив интервалов, берем первый элемент, бежим по массиву и смотрим нет ли пересечений, если пересечений не нашлось - увеличиваем время, а первый элемент удаляем. если нашлось пересечение - объеденяем и все снова
Eyeless Watcher
Цитата(dreamflyer @ 13.06.2012, 5:51) *
есть массив интервалов, берем первый элемент, бежим по массиву и смотрим нет ли пересечений, если пересечений не нашлось - увеличиваем время, а первый элемент удаляем. если нашлось пересечение - объеденяем и все снова

Квадратичная сложность от количества интервалов, плохо.
dreamflyer
согласен, но зато прозрачней, а судя по контексту сложность тут совсем не критична, да и автор в лучшем случае пузырьком скорее всего сортировать будет, поэтому без разницы.
idle
На sql, наверное, можно сделать select начал интервалов, сгруппировать по ним и взять максимальное значение концов интервалов начинающихся в этой точке, добавить select минимального значения начала любого интервала начинающегося после этой точки. Потом взять минимальное из последних двух значений:

SELECT t2.start, CASE WHEN ((t2.nextstart IS NULL) OR (t2.stop < t2.nextstart)) THEN t2.stop ELSE t2.nextstart END FROM (SELECT start, MAX(stop) AS stop, (SELECT MIN(start) FROM times WHERE (start > t1.start)) AS nextstart FROM times AS t1 GROUP BY t1.start) AS t2

Другой вариант - сделать вспомогательную таблицу из маленьких интервалов, покрывающих нужный диапазон времени, потом join-ом оставить интервалы, которые пересекаются с имеющимися отрезками времени (с округлением). Оставить только уникальные:

SELECT DISTINCT(a.start), a.stop FROM aux a JOIN times t ON ((a.start < t.stop) AND (a.stop > t.start)) -- округление в плюс
idle
Цитата(idle @ 23.06.2012, 15:54) *
На sql, наверное, можно сделать select начал интервалов, сгруппировать по ним и взять максимальное значение концов интервалов начинающихся в этой точке, добавить select минимального значения начала любого интервала начинающегося после этой точки. Потом взять минимальное из последних двух значений:


Здесь ошибка. Надо брать максимальное значение концов интервалов начинающихся в этой точке или раньше:

SELECT t2.start, CASE WHEN ((t2.nextstart IS NULL) OR (t2.stop < t2.nextstart)) THEN t2.stop ELSE t2.nextstart END FROM (SELECT start, (SELECT MAX(stop) FROM times WHERE (start <= t1.start)) AS stop, (SELECT MIN(start) FROM times WHERE (start > t1.start)) AS nextstart FROM times AS t1 GROUP BY t1.start) AS t2
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Русская версия IP.Board © 2001-2024 IPS, Inc.