Вопрос по javascript, jquery, algorithm – Пользовательский календарь с событиями

9

Я работаю над системой событий, которая в основном представляет собой контейнер с высотой 720 пикселей, каждый пиксель представляет одну минуту с 9:00 до 21:00 и шириной 620 пикселей (отступы 10 пикселей слева и справа).

Естественным требованием для календарной системы является то, что:

The objects should be laid out so that they do not visually overlap. If there is one event in a time slot, its width will be 600px Every colliding event must be the same width as every other event that it collides width. An event should use the maximum width possible while still adhering to the first constraint.

enter image description here

На входе будет массив что-то вроде:

[
 {id : 1, start : 30, end : 150},  // an event from 9:30am to 11:30am
 {id : 2, start : 540, end : 600}, // an event from 6pm to 7pm
 {id : 3, start : 560, end : 620}, // an event from 6:20pm to 7:20pm
 {id : 4, start : 610, end : 670} // an event from 7:10pm to 8:10pm
]

Я создал нужный макет, но я застрял с частью JavaScript :( Это то, что я до сих пор:

var Calendar = function() {

   var layOutDay = function(events) {
     var eventsLength = events.length;

     if (! eventsLength) return false;

     // sort events
     events.sort(function(a, b){return a.start - b.start;});

     for (var i = 0; i < eventsLength; i++) {
         // not sure what is next
     }         

   };

   return {
       layOutDay : layOutDay,
   }

}();

Необходимо создать элементы div и расположить их в соответствии с вышеуказанными требованиями.

Пожалуйста, смотрите демо JSBin.

Любая помощь будет оценена.

Gravigigging, да, но я чувствую, что нужно объяснить, почему автору нужно изобретать велосипед: это проблема кодирования для заявления о приеме на работу. Эта графика буквально является той же самой графикой, которую они отправляют вместе со своим документом спецификации вызова. Я почти уверен, что условия конкурса должны были быть конфиденциальными. Упс. Интересно, получил ли он работу? Если нет, то одна из причин, вероятно, заключалась в том, что он разместил это на SO. Adrian
Просто убедившись, что я понимаю: ваша проблема вообще не связана с графикой, и ее можно сформулировать следующим образом: вам дается N начальных и конечных точек (s_i, e_i), и для каждого i вам необходимо определить, как многие другие моменты, с которыми он пересекается. Это решит вашу проблему? Guy Adini
Это связано с графикой, потому что вы можете иметь три первых перекрывающихся события, одно из которых очень длинное, а затем самое длинное событие перекрывается с другим событием X. Даже если X перекрывается только одним событием, его ширина не может быть 1/2 ширины столбца, потому что он разделяет пространство с событием, графическая ширина которого составляет 1/3. Так что все сложнее. Antti Huima
... и расположение также зависит от горизонтального упорядочения событий, потому что если у вас есть очень длинное событие между двумя короткими событиями, длинное событие проходит через столбец на всю его вертикальную длину. Поэтому необходимо учитывать и горизонтальное упорядочение. Antti Huima
Зачем изобретать велосипед? Почему бы не использовать что-то вроде Arshaw.com / fullcalendar или Web-delicious.com / JQuery-события-календарь-wdcalendar? eggyal

Ваш Ответ

6   ответов
7

http: //jsbin.com/igujil/13/edit#previe

Как видите, решить эту проблему непросто. Позвольте мне рассказать вам, как я это сделал.

Первый шаг, помеченный Шаг 0, чтобы убедиться, что события отсортированы по id. Это облегчит нашу жизнь, когда мы начнем играть с данными.

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

Шаг 2 Обратите внимание, что я добавил проверку, чтобы убедиться, что событие начинается до его окончания. Немного защиты, но мой алгоритм попадет в бесконечный цикл с неверными данными, поэтому я хочу убедиться, что события имеют смысл.

В конце этого цикла наш массив временных интервалов будет выглядеть так:

0: []
1: []
...
30: [1]
31: [1]
...
(пропуская некоторые интересные цифры)
540: [2]
560: [2,3]
610: [3,4]

Я рекомендую вам добавитьconsole.log(timeslots) незадолго до шага 3, если вы растеряны / любопытны. Это очень важная часть решения, и следующий шаг намного сложнее объяснить.

Шаг - это место, где мы разрешаем конфликты планирования. Каждое событие должно знать две вещи:

Максимальное количество конфликтов. Горизонтальное упорядочение (чтобы конфликты не перекрывались).

(1) легко из-за того, как хранятся наши данные; ширина массива каждого временного интервала - это число событий. Временной интервал 30, например, имеет только 1 событие, потому что событие # 1 является единственным в то время. В Таймслоте 560, однако, у нас есть два события, поэтому каждое событие (# 2 и # 3) получает счетчик два. (И если бы была строка с тремя событиями, все они получили бы счет три и т. Д.)

(2) немного более тонкий. Событие № 1 достаточно очевидно, потому что оно может охватывать всю ширину календаря. Событие № 2 должно будет уменьшить его ширину, но оно все равно может начаться вдоль левого края. Событие № 3 не может.

Мы решаем это с помощью переменной временного интервала, которую я назвалnext_hindex. Он начинается с 0, потому что по умолчанию мы хотим располагаться вдоль левого края, но он будет увеличиваться каждый раз, когда мы находим конфликт. Таким образом, следующее событие (следующий фрагмент нашего конфликта) начнется со следующей горизонтальной позиции.

Шаг 4 немного проще. При вычислении ширины используется максимальное число конфликтов, полученное на шаге 3. Например, если мы знаем, что у нас есть 2 события в 5:50, мы знаем, что каждое событие должно быть в 1/2 от ширины календаря. (Если бы у нас было 3 события, каждое было бы 1/3 и т. Д.) Положение х рассчитывается аналогично; мы умножаем на hindex, потому что хотим компенсировать ширину (число конфликтных) событий.

Наконец, мы просто создаем небольшой DOM, размещаем наши события div и устанавливаем случайный цвет, чтобы их было легко отличить друг от друга. Результат (я думаю) то, что вы искали.

Если у тебя есть вопросы, я с удовольствием на них отвечу. Я знаю, что это, вероятно, больше кода (и больше сложности), чем вы ожидали, но это была удивительно сложная проблема для решения:)

Я просто хочу отметить, что это «решение» не работает при сложных наборах данных. Jsbin.com / igujil / 114 / редактировать Впрочем, хорошие усилия. Adam
2


ДЕМО:http: //jsfiddle.net/CBnJY/11

var Calendar = function() {
var layOutDay = function(events) {
    var eventsLength = events.length;

    if (!eventsLength) return false;

    // sort events
    events.sort(function(a, b) {
        return a.start - b.start;
    });

    $(".timeSlot").each(function(index, val) {
        var CurSlot = $(this);
        var SlotID = CurSlot.prop("SlotID");
        var EventHeight = CurSlot.height() - 1;
        //alert(SlotID);
        //get events and add to calendar
        var CurrEvent = [];
        for (var i = 0; i < eventsLength; i++) {
            // not sure what is next
            if ((events[i].start <= SlotID) && (SlotID < events[i].end)) {
                CurrEvent.push(events[i]);
            }
        }

        var EventTable = $('<table style="border:1px dashed purple;width:100%"><tr></tr></table');
        for (var x = 0; x < CurrEvent.length; x++) {
            var newEvt = $('<td></td>');
            newEvt.html(CurrEvent[x].start+"-"+CurrEvent[x].end);
            newEvt.addClass("timeEvent");
            newEvt.css("width", (100/CurrEvent.length)+"%");
            newEvt.css("height", EventHeight);
            newEvt.prop("id", CurrEvent[x].id);
            newEvt.appendTo(EventTable.find("tr"));
        }
        EventTable.appendTo(CurSlot);
    });

};

return {
    layOutDay: layOutDay
}
}();

var events = [
{
id: 1,
start: 30,
end: 150},
{
id: 2,
start: 180,
end: 240},
{
id: 3,
start: 180,
end: 240}];

$(document).ready(function() {
var SlotId = 0;
$(".slot").each(function(index, val) {
    var newDiv = $('<div></div>');
    newDiv.prop("SlotID", SlotId)
    //newDiv.html(SlotId);
    newDiv.height($(this).height()+2);
    newDiv.addClass("timeSlot");
    newDiv.appendTo($("#calander"));
    SlotId = SlotId + 30;
});

// call now
Calendar.layOutDay(events);
});

Я настоятельно рекомендую использоватьhttp: //arshaw.com/fullcalendar
demo:http: //jsfiddle.net/jGG34/2
То, что вы пытаетесь достичь, уже реализовано в этом, просто включите дневной режим и сделайте несколько хаков CSS ... вот и все !!

1

Требовани

Часть I: Напишите функцию для размещения серии событий в календаре на один день.

События будут помещены в контейнер. Верхняя часть контейнера представляет 9 утра, а нижняя представляет 9 вечер
Ширина контейнера будет 620 пикселей (отступы 10 пикселей слева и справа), а высота будет 720 пикселей (1 пиксель за каждую минуту между 9:00 и 21:00). Объекты должны быть расположены так, чтобы они не перекрывались визуально. Если в данный временной интервал есть только одно событие, его ширина должна составлять 600 пикселе

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

См. Изображение ниже для примера.

Входными данными для функции будет массив объектов события с временем начала и окончания события. Пример (JS):

[

     {id : 1, start : 60, end : 120},  // an event from 10am to 11am
     {id : 2, start : 100, end : 240}, // an event from 10:40am to 1pm
     {id : 3, start : 700, end : 720} // an event from 8:40pm to 9pm 
]

Функция должна возвращать массив объектов событий с установленными левой и верхней позициями (относительно верхнего левого угла контейнера), в дополнение к идентификатору, времени начала и окончания.

Часть II. Используйте свою функцию из части I для создания веб-страницы, стилизованной под изображение, приведенное ниже.
со следующими событиями календаря:

Событие, которое начинается в 9:30 и заканчивается в 11:30 Событие, которое начинается в 6:00 вечера и заканчивается в 7:00 вечер Событие, которое начинается в 6:20 вечера и заканчивается в 7:20 вечер Событие, которое начинается в 7:10 вечера и заканчивается в 8:10 вечераКо Установка и запуск Клонировать это репо Откройте файл index.html в своем любимом браузере.

Заметка при запуске присутствует набор событий по умолчанию (требуется во второй части).
Для тестирования, прямо под массивом по умолчанию (строка 14), вы можете найтиgenerateEvents функция, которая генерирует случайный массив событий. Размер массива будет определяться атрибутом arrayLength.

@ Зависимос

никто

Решени

Ниже вы можете найти алгоритм решения проблемы в соответствии с требованиями.

Введени

Я постараюсь решить эту задачу в виде графиков, поэтому нужно дать несколько терминов.

Услови

Узел представляет событие - $ n $, $ n \ in N, N $ - группа всех узлов.
Edge: представляет сталкивающиеся события - $ e $, $ e \ in E, E $ - группа всех ребер. Например, если сталкиваются узлы $ u $ и $ v $, то между ними будет ребро $ e_ {u, v} $.
Graph: набор узлов и ребер $ G, G \ in (N, E) $.
Cluster: представляет группу связанных узлов (подгруппа Графа) - $ c $, $ c \ subseteq G $. Например, если у нас есть следующие узлы: $ u, v, w $ и ребро $ e_ {u, v} $. Тогда будет 2 кластера, первый будет содержать $ u, v $, а второй будет содержать только $ w $.
Клика представляет подгруппу узлов в кластере, каждая пара узлов в этой группе имеет соединительное ребро - $ cq $, $ cq \ subseteq c $. Обратите внимание, что клика представляет группу встречных событий.

Board: Дневной контейнер, содержащий все события.

Условия

Для следующего ввода:

[
     {id : 1, start : 0, end : 120}, 
     {id : 2, start : 60, end : 120},
     {id : 3, start : 60, end : 180},
     {id : 4, start : 150, end : 240},
     {id : 5, start : 200, end : 240},
     {id : 6, start : 300, end : 420},
     {id : 7, start : 360, end : 420},
     {id : 8, start : 300, end : 720}
]

График будет:

Черный цикл - узел - событие
Зеленый эллипс - клика - группа встречных событий
Красный эллипс - кластер - группа связанных узлов
Синяя линия - край - соединитель между встречными событиями
Примечание: верхний левый зеленый эллипс - самая большая клика в левом кластере.
Доска будет:

Красный прямоугольник - кластер
Цветные точки - клика (каждый цвет - это отдельная клика).

Парафраз ограничения Каждый узел в один кластер должна иметь одинаковую ширину на доске, чтобы соответствовать первому ограничению. Узлы не должны накладываться друг на друга на плате, пока не набросаны до максимальной ширины и все еще придерживаются первого ограничения. Ширина узлов в кластере будет установлена самой большой кликой в кластере. Это верно, потому что узлы в одной и той же клике будут использовать на плате как минимум одну минуту, что означает, что они должны иметь одинаковую ширину (потому что они сталкиваются). Таким образом, другие узлы в кластере будут иметь такую же ширину, как и самый маленький узел. Каждый узел в клике получит свою позицию оси X относительно своих соседей.Алгорит

Для данного массива событийarrayOfEvents (из примера требований):

[

     {id : 1, start : 60, end : 120},  // an event from 10am to 11am
     {id : 2, start : 100, end : 240}, // an event from 10:40am to 1pm
     {id : 3, start : 700, end : 720} // an event from 8:40pm to 9pm 
]

Первый шаг создание гистограммы событий.
Будет создан массив массивов, давайте назовем этот массив какhistogram.histogram длина будет 720, каждый индексhistogram будет представлять минуту на доске (день). Позволяет назвать каждый индексhistogram a minute. Каждыйminute, это сам массив. Каждый индексminute array представляет событие, которое происходит в эту минуту.

pseudo код:

histogram = new Array(720); 

forEach minute in histogram:
    minute = new Array(); 

forEach event in arrayOfEvents:
    forEach minute inBetween event.start and endMinute:
        histogram[minute].push(event.id);

histogram массив будет выглядеть следующим образом (для данного примера):

[
    1: [],
    2: [],
    .
    .
    .
    59: [],
    60: [1],
    61: [1],
    .
    .
    .
    99: [1],
    100: [1,2],
    101: [1,2],
    .
    .
    .
    120: [1,2],
    121: [2],
    122: [2],
    .
    .
    .
    240: [2],
    241: [],
    242: [],
    .
    .
    .
    699: [],
    700: [3],
    701: [3],
    .
    .
    .
    720: [3]
]

Шаг второй создание графа
На этом шаге будет создан график, включающий узлы, соседние узлы и кластеры, а также будет определена самая большая клика кластера.
Обратите внимание, что не будет граничного объекта, каждый узел будет содержать карту узлов (ключ: идентификатор узла, значение: узел), с которой он сталкивается (его соседи). Эта карта будет называться соседями. ТакжеmaxCliqueSizeтрибут @ будет добавлен к каждому узлу.maxCliqueSize - самая большая клика, частью которой является узел.

pseudo код:

nodesMap := Map<nodeId, node>;
graph := Object<clusters, nodesMap>;
Node := Object<nodeId, start, end, neighbours, cluster, position, biggestCliqueSize>;
Cluster := Object<mapOfNodesInCluster, width>

//creating the nodes
forEach event in arrayOfEvents {
    node = new Node(event.id, event.start, event.end, new Map<nodeId, node>, null)
    nodeMap[node.nodeId] = node;
 }

//creating the clusters
cluster = null;
forEach minute in histogram {
    if(minute.length > 0) {
        cluster = cluster || new Cluster(new Array(), 0);
        forEach eventId in minute {
            if(eventId not in cluster.nodes) {
                cluster.nodes[eventId] = nodeMap[eventId];
                nodeMap[eventId].cluster = cluster;
            }
        } 
    } else { 
        if(cluster != null) {
            graph.clusters.push(cluster);
        }

        cluster = null;
    }
}

//adding edges to nodes and finding biggest clique for each node
forEach minute in histogram {
    forEach sourceEventId in minute {
        sourceNode = eventsMap[sourceEventId];
        sourceNode.biggestCliqueSize = Math.max(sourceNode.biggestCliqueSize, minute.length);
        forEach targetEventId in minute {
            if(sourceEventId != targetEventId) {
                sourceNode.neighbours[targetEventId] = eventsMap[targetEventId];
            }
        }
    }
}

Шаг третий: вычисление ширины каждого кластера.
Как упоминалось выше, ширина всех узлов в кластере будет определяться размером самой большой клики в кластере.
Ширина каждого узла $ n $ в кластере $ c $ будет соответствовать следующему уравнению:
$ n_ {width} = \ frac {Board_ {width}} {Max \ left (n_ {1} .biggestCliqueSize, n_ {2} .biggestCliqueSize, ..., n_ {n} .biggestCliqueSize \ right)} $ $

ирина каждого узла будет установлена в кластере, с которым он связан. Таким образом, свойство width будет установлено для объекта кластера.

pseudo код:

forEach cluster in graph.clusters {
    maxCliqueSize = 1;
    forEach node in cluster.nodes {
        maxCliqueSize = Max(node.biggestCliqueSize, sizeOf(node.clique);
    }
    cluster.width = BOARD_WIDTH / maxCliqueSize; 
    cluster.biggestCliqueSize = biggestCliqueSize;
}

Шаг четвертый: вычисление положения узла в его клике.
Как уже упоминалось, узлам придется делить ось X («недвижимость») со своими соседями. На этом шаге положение оси X будет задано для каждого узла в соответствии с его соседями. Самая большая клика в кластере будет определять количество доступных мест.

pseudo код:

forEach node in nodesMap {
    positionArray = new Array(node.cluster.biggestCliqueSize);
    forEach cliqueNode in node.clique {
        if(cliqueNode.position != null) {
            //marking occupied indexes
            positionArray[cliqueNode.position] = true;
        }
    }

    forEach index in positionArray {
        if(!positionArray[index]) {
            node.position = index;
            break;
        }
    }
}

Шаг пятый: Размещение узлов на доске. На этом этапе у нас уже есть вся информация, необходимая для размещения события (узла) на его позиции на доске. Положение и размер каждого узла будет определяться:

height: node.end - node.startwidth: node.cluster.width top-offset: node.start left-offset: node.cluster.width * node.position + left-padding Сложность алгоритма

Временная сложность алгоритма составляет $ O \ left (n ^ {2} \ right) $.
Пространственная сложность алгоритма $ O \ left (n \ right) $.

Github репо:https: //github.com/vlio20/one-da

0

A Делитель это любой момент в течение дня, когда нет события Кресты. Таким образом, если у вас есть одно событие с 9 до 11 часов, а другое с 11 до 13 часов, и никаких других событий, разделитель будет в 11 часов, и в любое время в 13 часов или позже, и в любое время в 9 часов. утра или раньше.

Я бы делил каждый день на набор «событийных промежутков времени», которые представляют собой максимальные промежутки времени, не содержащие делителей. Для каждого насыщенного промежутка времени я вычисляю максимальное количество одновременно перекрывающихся событий и использую его в качестве «номера столбца» для этого отрезка события. Затем я жадно расположил бы каждый отрезок времени на рассчитанное количество столбцов, чтобы каждое событие было расположено как можно левее, в порядке времени начала событий.

Так, например, следующий график:

A  9 am - 11 am
B 10 am - 12 pm
C 10 am -  1 pm
D  1 pm  - 2 pm
E  2 pm  - 5 pm
F  3 pm  - 4 pm

будет обработан следующим образом. Промежуточные промежутки времени: с 9:00 до 13:00, с 13:00 до 14:00 и с 14:00 до 17:00, так как в 13:00 и 14:00 есть разделители (нет мероприятия Кресты те времена)

В первом интервале максимум три события перекрываются, во втором - только одно, а в третьем - два.

Столбцы расположены следующим образом:

 9 am - 10 am  |   |   |   |
10 am - 11 am  |   |   |   |
11 am - 12 pm  |   |   |   |
12 pm -  1 pm  |   |   |   |___ end of first e.t.s.
 1 pm -  2 pm  |           |___ end of second e.t.s.
 2 pm -  3 pm  |     |     |
 3 pm -  4 pm  |     |     |
 4 pm -  5 pm  |     |     |

После чего события заполняются в хронологическом порядке:

 9 am - 10 am  | A |###|###|
10 am - 11 am  |_A_| B | C |
11 am - 12 pm  |###|_B_| C |
12 pm -  1 pm  |###|###|_C_|
 1 pm -  2 pm  |_____D_____|
 2 pm -  3 pm  |  E  |#####|
 3 pm -  4 pm  |  E  |__F__|
 4 pm -  5 pm  |__E__|#####|

что выглядит очень разумно. # обозначает свободное место

+ 1, но было бы полезно, если бы вы могли посмотреть демоверсию jsbin о том, как ее реализовать. Благодарност Dev555
Ну, например то, что событие получает полную ширину, если оно начинается раньше, чем другие события, это просто визуальный трюк, который может быть реализован на этапе постобработк Antti Huima
0

входные данные представляют собой список событий с начальным и конечным временем, а для каждого события выходными данными являются номер столбца этого события и общее количество столбцов во время этого события. Вам в основном нужно покрасить interval graph; вот какой-то псевдокод.

Для каждого событияe, сделай два "мгновения" (начало,e) и конец,e) указывая назад наe.

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

Инициализировать пустой списокcomponent, пустой списокcolumn_stack, числоnum_columns = 0 и числоnum_active = 0. component содержит все события, которым будет присвоено одинаковое количество столбцов.column_stack запоминает, какие столбцы свободны.

Проверять моменты в порядке. Если это момент начала событияe, тогда нам нужно назначитьe столбец. Получить этот столбец, нажавcolumn_stack если не пусто; в противном случае назначьте новый столбец (числоnum_columns) и увеличениеnum_columns (другой порядок для индексации на основе 1 вместо 0 на основе). Добавитьe вcomponent. Инкрементnum_active. Если это конец, то нажмитеeазначенный столбец @ наcolumn_stack. Декрементnum_active. Еслиnum_active теперь равно 0, тогда мы начинаем новый связанный компонент, выталкивая все события изcomponent и установив общее количество столбцов вnum_columns с последующей очисткойcolumn_stack и сбросnum_columns до 0.

0

. Для этого есть довольно простой алгоритм:

сортировать массив встречappointments по дате начала и разрыв связи с датой окончания. поддерживать массивactive со всеми активными встречами, который в начале пу сохранить значениеcollision для каждой встречи (поскольку у вас уже есть объекты, вы можете сохранить их как другое свойство)[{id : 1, start : 30, end : 150, collisions : 0},...]

проходить черезappointments со следующими шагами:

переместить первый элемент i) отappointments сравнить дату начала сi с окончанием всех элементовj вactive - удалить все элементы, гдеj.enddate < i.startdate Обновить коллизии от всех оставшихсяj (+1 за каждого) обновление столкновенияi ( i.collision = active.length)popi в массивactive

повторите эти шаги для всех элементовappointments.

Пример

(будьте осторожны, псевдокод):

var unsorted = [7,9],[2,8],[1,3],[2,5],[10,12]
// var appointments = sort(unsorted);
var appointments = [1,3],[2,5],[2,8],[7,9],[10,12]

// now for all items of appoitments:
for (var x = 0; x<appointments.length;x++){
    var i = appointments[x];                 // step 1
    for (var j=0; j<active.length;j++){      
     // remove j if j.enddate < j.startdate  // step 2
     // else j.collision += 1;               // step 3
    }
    i.collision = active.length;             // step 4
    active.pop(i);                           // step 5
}

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

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

Я думаю, что твоя помощь все еще нужна для выполнения твоего плана. Благодарност Dev555

Похожие вопросы