Алгоритм вычисления, максимального колличества пересечений времен

← →
DelphiN! © (2007-12-12 12:45) [0]

Есть таблица с логом сеансов игр в компьютерном клубе

Computer_ Game_ StartTime EndTime
k1 Q3 01.11.2007 00:01:18 01.11.2007 00:31:18
k2 Q3 01.11.2007 00:32:18 01.11.2007 00:42:18
... .. ........................... ............................
... .. ........................... ............................
... .. ........................... ............................

скажем за 1 месяц

необходимо вычислить сколько человек играло одновременно в одну игру максимально(максимально много) за определённый период

Допустим если 01го января в одну игру одновременно играли 10 человек, а 2го - 20, то нужно вывести 20

Как реализовать алгоритм я придумать не могу :(

← →
Sergey13 © (2007-12-12 12:54) [1]

> [0] DelphiN! © (12.12.07 12:45)

А что значит одновременно? Начали играть 10 человек, потом, не заканчивая игры полностью, 5 ущли, но пришли еще 10. Сколько играло одновременно?

← →
korneley © (2007-12-12 12:57) [2]

> Как реализовать алгоритм я придумать не могу :(
Что именно, алгоритм пересечения(вхождения) одного диапазона с(в) другим(ой), или поиска макс. значения в массиве?

← →
DelphiN! (2007-12-12 13:14) [3]

> Sergey13 © (12.12.07 12:54) [1]
>

> А что значит одновременно? Начали играть 10 человек, потом,
> не заканчивая игры полностью, 5 ущли, но пришли еще 10.
> Сколько играло одновременно?

Если в одну игру играло 10 человек, 5 ушли, но пришли еще 10 и начали играть в ту же игру. То максимально много играющих было 15 человек

> korneley © (12.12.07 12:57) [2]

Я тоже вначале думал что все очень просто, но когда приступил к реализации все оказалось гораздо сложнее.
Например: Если 1 человек играл в игру с 00:00:00 до 08:00:00, и во время этого периода к нему подключались еще 10 человек, каждый из которых подключался не одновременно с остальными девятью. Получается что максимальное количество одновременно играющих должно быть равно 2, а не 11. Как этого добиться?

← →
Рамиль © (2007-12-12 13:17) [4]

Пересечение.

← →
Ld (2007-12-12 13:17) [5]

> Я тоже вначале думал что все очень просто, но когда приступил
> к реализации все оказалось гораздо сложнее.
> Например: Если 1 человек играл в игру с 00:00:00 до 08:
> 00:00, и во время этого периода к нему подключались еще
> 10 человек, каждый из которых подключался не одновременно
> с остальными девятью. Получается что максимальное количество
> одновременно играющих должно быть равно 2, а не 11. Как
> этого добиться?

Сколько одновременно занято компьютеров? Сколько одновременно играют в одну и туже игру сами по себе? Сколько играют в одну и туже игру по сети вместе? Сколько играют в одну и туже игру по сети в различных группах?

← →
Ld (2007-12-12 13:18) [6]

*ту же

← →
boriskb © (2007-12-12 13:21) [7]

Круглосуточно клуб работает?

← →
Рамиль © (2007-12-12 13:21) [8]

Если в лоб, то сортируешь все отрезки времени по возрастанию начала отрезка. Для каждого отрезка вычисляешь пересечение с отрезками, начало которых находится в пределах текущего отрезка.

← →
DelphiN! (2007-12-12 13:22) [9]

> Ld (12.12.07 13:17) [5]

Сколько, максимально много человек играли в одну и туже игру одновременно.

← →
Sergey13 © (2007-12-12 13:33) [10]

> [9] DelphiN! (12.12.07 13:22)

Все таки "одновременно" - это слишком размытое понятие в этом случае. Тем более не на момент, а за период времени.
Тут, ИМХО, можно только сканировать диапазон дат примерно таким запросом
select game_,count(computer_) from table_name where StartTime<:KT and EndTime>:KT
в цикле с какой то эмпирической дискретностью.
Ну и определять максимум полученного значения.

← →
Anatoly Podgoretsky © (2007-12-12 13:33) [11]

> Рамиль (12.12.2007 13:21:08) [8]

Думаешь так просто

*********************
---*********------------
-----***********************
**********--

← →
Anatoly Podgoretsky © (2007-12-12 13:35) [12]

> Sergey13 (12.12.2007 13:33:10) [10]

Дискретно определяется единицами измерения, если в учете фигурируют миллисекунды, то 1 мс

← →
Sergey13 © (2007-12-12 13:39) [13]

> [12] Anatoly Podgoretsky © (12.12.07 13:35)

Никто не запретит использовать любую "единицу", например "5 минут" или даже "полчаса". 8-)

← →
DelphiN! (2007-12-12 13:45) [14]

> boriskb © (12.12.07 13:21) [7]

Да, круглосуточно

> Рамиль © (12.12.07 13:21) [8]

А если основной отрезок с 5ти до 11ти, а сравниваемый с 9ти до 12ти, получается что они играли вместе(с 9ти до 11), но 5 не находится в пределах с 9ти до 12ти

← →
Anatoly Podgoretsky © (2007-12-12 13:50) [15]

> DelphiN! (12.12.2007 13:45:14) [14]

Вот ты уже двигаешь к группированию.

← →
DelphiN! (2007-12-12 13:53) [16]

> Sergey13 © (12.12.07 13:33) [10]

Это будет выполнятся через чур долго

← →
boriskb © (2007-12-12 13:59) [17]

Я бы сначала сделал в лоб:
Каждый интервал сравнивал с каждым на предмет пересечения.
Интервал, в котором максимальное количество пересечений - искомый
Ясно, что не эффективно, но думаю, что два десятка компов (так?) даже за месяц обсчитать будет не накладно.
А когда уже будет считать, тогда уже подумать (если приспичит) об улучшении алгоритма.
От твоей статистики зависит, например:
Надо искать пересечения интервалов, отстраненных друг от друга больше чем на сутки? На двое?
Сидят у тебя по стольку?

← →
Рамиль © (2007-12-12 14:00) [18]

> А если основной отрезок с 5ти до 11ти, а сравниваемый с
> 9ти до 12ти, получается что они играли вместе(с 9ти до 11),
> но 5 не находится в пределах с 9ти до 12ти

Но 9 находится в пределах 5-11.
> Anatoly Podgoretsky © (12.12.07 13:33) [11]

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

← →
DelphiN! (2007-12-12 14:08) [19]

> boriskb © (12.12.07 13:59) [17]

> Рамиль © (12.12.07 14:00) [18]

Тогда ситуация :

Пришли 3ое, один зашел в игру :

09 - 12
2ой 10 - 10.05
3ий 11 - 11.05

Ваш способ покажет что одновременно играли трое, но на самом деле лишь двое

← →
DelphiN! (2007-12-12 14:09) [20]

> Anatoly Podgoretsky © (12.12.07 13:50) [15]

> Вот ты уже двигаешь к группированию.

Что за группирование? Можно поподробнее?

← →
data © (2007-12-12 14:10) [21]

в свое время делала нечто подобное, может не оптимально, но работало:
- каждый интервал представляется 2мя временными точками - начало и конец.
- каждая временная точка представляется записью с полями 1) время, 2) номер интервала (игрока) (впринципе можно и без него, но может в дальнейшем понадобиться для какой-н другой статистики) 3) признак точки, чем она является : начало/конец интервала
- заполняется массив из таких записей
- массив сортируется любым удобным способом
- потом проходим по массиву встречаем начало интервала - прибавляем к некоему счетчику +1, конец интервала -1. Значение счетчика после каждой операции прибавления сравниваем с переменной, где хранится его максимум.

← →
boriskb © (2007-12-12 14:11) [22]

> Ваш способ покажет что одновременно играли трое, но на самом
> деле лишь двое

Мой способ покажет двоих, так как третьего я буду сравнивать не с первым, а уже с пересечением 1 и 2

забыла главное - массив сортируется по полю записей, где лежит время. :)

> DelphiN! (12.12.2007 13:53:16) [16]

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

> Рамиль (12.12.2007 14:00:18) [18]

Ну на тебе другой пример

********************************
--***----------***-------------------
------**-------------------------------
-----------***------------------------
-------****---------------------------
---*********************----------

Разговор то бессмысленен, без технического задания, но задача точно связано с группированием по интервалам

Вот общая схема запроса:
SELECT COUNT(DISTINCT T1.ID) FROM Table T1 JOIN Table T2 ON minimum(T1.EndTime,T2.EndTime) > maximum(T1.StartTime,T2.StartTime) WHERE (<компьютер=XXX>) AND (<проверка "определённого периода">)
где ID - уникальный идентификатор записи.

> Рамиль (12.12.2007 14:38:26) [26]

Да не в этом дело, а в неопределенности у автора понятия одновременность.

> Да не в этом дело, а в неопределенности у автора понятия
> одновременность.

Гдеж там неопределенность.
Найти множество, являющееся пересечением максимально возможного количества данных множеств.

> Рамиль (12.12.2007 14:52:29) [29]

Это твое определение, а не автора. Он и слов то таких не знает.

> Рамиль (12.12.2007 14:52:29) [29]

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

Алгоритм вычисления, максимального колличества пересечений времен Найти похожие ветки