На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
  
> Уплотнение списка временных отрезков
    Доброго времени суток всем!

    Такая проблема: в качестве input'a получаю пары дат. Поступают они конечно не по порядку. Некоторые из них пересекаются, некоторые - "соприкасаются", остальные - нет. Необходимо все пересекающиеся и прилежащие связать воедино, т.е. максимально уплотнить список.

    Например: (01.01.2018, 02.01.2018), (15.02.2018, 21.03.2018), (10.01.2018, 10.01.2018), (03.01.2018, 09.01.2018)

    Желаемый итог: (01.01.2018, 10.01.2018), (15.02.2018, 21.03.2018)


    Нет ли более-менее подходящего готового решения?
      1. Сортируем список по первой дате в паре.
      2. Создаем результирующую пару, равную текущей (на первом шаге - первой).
      3. Берем следующую пару.
      4. Идем по списку:если
        ExpandedWrap disabled
          $вторая дата в результирующую пару$ - $первая дата в следующей паре$ >= 0 и $вторая дата в следующей паре$ > $вторая дата в результирующую пару$
        , то вторую дату в результирующей паре сдвигаем на второю дату из другой пары и повторяем с шага 3; если нет - сохраняем результирующую пару в выходной список и переходим к шагу 2.
      Сообщение отредактировано: Profi -
        Profi, имо, твое решение для етой задачи не подходит. Ты решаешь задачу со для статическим набором данных. В задаче - поток данных.
          >В задаче - поток данных.
          Откуда это следует?


          Создать для всех начал и концов пары (время, признак +/-1 для начала или конца соответственно), причём концы увеличиваем на 1 для обеспечения сцепления.

          Отсортировать список пар по времени. Если время совпадает, то признак - вторичный ключ, +1 идёт раньше -1 (опять же для обеспечения сцепления)

          Завести счётчик активных интервалов.

          Пройти по результату, изменяя счётчик на величину признака

          Если счётчик переходит из 0 в 1 - начать новый интервал для результата.

          Если счётчик переходит из 1 в 0 - закончить интервал, добавить его к результату.
            Цитата MBo @
            Откуда это следует?

            Цитата firelex @
            в качестве input'a получаю пары дат. Поступают они конечно не по порядку
              MIF

              Может, в этом и есть резон (я бы воспринял это как просто несортированный набор данных)

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

                Я, в принципе, вручную так все и делал.

                До вот этого
                Цитата
                причём концы увеличиваем на 1 для обеспечения сцепления.
                сам долго доходил (плюс еще начала уменьшаю на 1 - все для той же сцепки). Теперь всегда делаю только так - самый надежный вариант.

                Данные поступают из БД. Иногда готовым массивом, иногда - частями. Просто очень уж модуль удобный получается - применим в разных случаях.

                Жаль что готового класса нет. <_<
                  >плюс еще начала уменьшаю на 1
                  Это лишнее, если нет специальных условий сцепки - в таком случае интервалы 1-3 + 5-7 превратятся в 0-4 и 4-8 и объединятся.
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script execution time: 0,0345 ]   [ 17 queries used ]   [ Generated: 28.03.24, 11:16 GMT ]