Custom calendar with event divs

Question

I am working on an event system which is basically a container with 720px height with each pixel representing one minute from 9AM to 9PM and has width of 620px (10px padding from left and right)

The natural requirement for the calendar system is that:

• 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.

The input will be an array something like:

[
 {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
]

I have created the needed layout but I am stuck with JavaScript part :( This is what I have so far:

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,
   }

}();

Need to create divs and position them as per above requirements.

Please see JSBin demo.

Any help will be greatly appreciated.

Answer 1

Here is my solution: # one-day A one day calendar

Requirements

Part I: Write a function to lay out a series of events on the calendar for a single day.

Events will be placed in a container. The top of the container represents 9am and the bottom represents 9pm.
The width of the container will be 620px (10px padding on the left and right) and the height will be 720px (1 pixel for every minute between 9am and 9pm). The objects should be laid out so that they do not visually overlap. If there is only one event at a given time slot, its width should be 600px.

There are 2 major constraints: 1. Every colliding event must be the same width as every other event that it collides width. 2. An event should use the maximum width possible while still adhering to the first constraint.

See below image for an example.

The input to the function will be an array of event objects with the start and end times of the event. Example (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 
]

The function should return an array of event objects that have the left and top positions set (relative to the top left of the container), in addition to the id, start, and end time.

Part II: Use your function from Part I to create a web page that is styled just like the example image below.
with the following calendar events:

1. An event that starts at 9:30 am and ends at 11:30 am
2. An event that starts at 6:00 pm and ends at 7:00pm
3. An event that starts at 6:20pm and ends at 7:20pm
4. An event that starts at 7:10pm pm and ends at 8:10 pm

Code

Installation & Running

1. Clone this repo
2. Open the index.html file in your favourite browser.

Note: at startup there is a default set of events (required in the second part).
For testing, right below the default array (line 14), you can find generateEvents function which generates random array of events. The array size will be determined by the arrayLength attribute.

Dependencies

none!

Solution

Below you can find the algorithm to solve the problem according to requirements.

Introduction

I will try to address this task in manner of graphs, so few terms should be given.

Terms

Node: represents an event - $n$, $n \in N, N$ - group of all nodes.
Edge: represents colliding events - $e$, $e \in E, E$ - group of all edges. For example, if node $u$ and $v$ collide then there will be an edge $e_{u,v}$ connecting them.
Graph: the collection of nodes and edges $G, G\in(N,E)$ .
Cluster: represents a group of connected nodes ( sub group of the Graph) - $c$, $c \subseteq G$ . For example, if we have the following nodes: $u, v, w$ and edge $e_{u,v}$. Then there will be 2 clusters, the first will contain $u,v$ and the second will contain only $w$.
Clique: represents sub group of nodes in a cluster, each pair of nodes in this group has a connecting edge - $cq$, $cq \subseteq c$. Note, a clique represents a group of colliding events.

Board: The day container which holds all the events.

Terms example

For the following input:

[
     {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}
]

The graph will be:

Black cycle - node - event
Green ellipse - clique - group of colliding events
Red ellipse - cluster - group of connected nodes
Blue line - edge - connector between colliding events
Note: the top left green ellipse is the biggest clique in the left cluster.
The board will be:

Red rectangle - cluster
Colored dots - clique (each color is a different clique).

Constraint paraphrase

1. Each node in the same cluster must have the same width on the board, in order to meet the first constraint.
2. Nodes must not overlap each other on the board while starching to maximum width and still adhering to the first constraint.
3. The width of nodes in a cluster will be set by the biggest clique in the cluster. This is true because, nodes in the same clique will share at least one minute on the board, meaning that they will have to have the same width (because they are colliding). So other nodes in the cluster will have the same width as the smallest node.
4. Each node in a clique will gain its X axis position relative to its neighbours.

Algorithm

For given array of events arrayOfEvents (from the requirements example):

[

     {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 
]

Step One: creating events histogram.
An Array of arrays will be created, lets call this array as histogram. The histogram length will be 720, each index of the histogram will represent a minute on the board (day). Lets call each index of the histogram a minute. Each minute, is an array itself. Each index of the minute array represents an event which takes place at this minute.

pseudo code:

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 array will look like this after this step (for given example):

[
    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]
]

Step Two: creating the graph
In this step the graph will be created, including nodes, node neighbours and clusters also the biggest clique of the cluster will be determined.
Note that there won't be an edge entity, each node will hold a map of nodes (key: node id, value: node) which it collides with (its neighbours). This map will be called neighbours. Also, a maxCliqueSize attribute will be added to each node. The maxCliqueSize is the biggest clique the node is part of.

pseudo code:

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];
            }
        }
    }
}

Step Three: calculating the width of each cluster.
As mentioned above, the width of all nodes in the cluster will be determined by the size of the biggest clique in the cluster.
The width of each node $n$ in cluster $c$ will follow this equation:
$$n_{width} = \frac{Board_{width}}{Max\left ( n_{1}.biggestCliqueSize, n_{2}.biggestCliqueSize, ..., n_{n}.biggestCliqueSize\right )}$$

Each node width will be set in the cluster its related to. So the width property will be set on the cluster entity.

pseudo code:

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;
}

Step Four: calculating the node position within its clique.
As already mentioned, nodes will have to share the X axis (the "real-estate") with its neighbours. In this step X axis position will be given for each node according to its neighbours. The biggest clique in the cluster will determine the amount of available places.

pseudo code:

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;
        }
    }
}

Step Five: Putting nodes on the board. In this step we already have all the information we need to place an event (node) on its position on the board. The position and size of each node will be determined by:

1. height: node.end - node.start
2. width: node.cluster.width
3. top-offset: node.start
4. left-offset: node.cluster.width * node.position + left-padding

Algorithm Complexity

The time complexity of the algorithm is $O\left(n^{2} \right )$.
The space complexity of the algorithm is $O\left (n \right )$.

Github repo: https://github.com/vlio20/one-day

Answer 2

If I understand you correctly, the input is a list of events with start and end times, and the output is, for each event, the column number of that event and the total number of columns during that event. You basically need to color an interval graph; here's some pseudocode.

1. For each event e, make two "instants" (start, e) and (end, e) pointing back to e.

2. Sort these instants by time, with end instants appearing before simultaneous start instants.

3. Initialize an empty list component, an empty list column_stack, a number num_columns = 0, and a number num_active = 0. component contains all of the events that will be assigned the same number of columns. column_stack remembers which columns are free.

4. Scan the instants in order. If it's a start instant for an event e, then we need to assign e a column. Get this column by popping column_stack if it's nonempty; otherwise, assign a new column (number num_columns) and increment num_columns (other order for 1-based indexing instead of 0-based). Append e to component. Increment num_active. If it's an end instant, then push e's assigned column onto column_stack. Decrement num_active. If num_active is now 0, then we begin a new connected component by popping all events from component and setting their total number of columns to num_columns, followed by clearing column_stack and resetting num_columns to 0.

Answer 3

Here is a working solution: http://jsbin.com/igujil/13/edit#preview

As you can see, it's not an easy problem to solve. Let me walk you through how I did it.

The first step, labelled Step 0, is to make sure the events are sorted by id. This will make our lives easier when we start playing with the data.

Step 1 is to initialize a 2-dimensional array of timeslots. For each minute in the calendar, we're going to make an array which will contain the events that take place during that minute. We do that in...

Step 2! You'll note I added a check to make sure the event starts before it ends. A little defensive, but my algorithm would hit an infinite loop on bad data, so I want to make sure the events make sense.

At the end of this loop, our timeslot array will look like this:

0: []
1: []
...
30: [1]
31: [1]
...
(skipping ahead to some interesting numbers)
540: [2]
560: [2,3]
610: [3,4]

I encourage you to add console.log(timeslots) just before Step 3 if you're confused/curious. This is a very important piece of the solution, and the next step is a lot more difficult to explain.

Step 3 is where we resolve scheduling conflicts. Each event needs to know two things:

1. The maximum number of times it conflicts.
2. Its horizontal ordering (so that conflicts don't overlap).

(1) is easy because of how our data is stored; the width of each timeslot's array is the number of events. Timeslot 30, for example, has only 1 event, because Event #1 is the only one at that time. At Timeslot 560, however, we have two events, so each event (#2 and #3) gets a count of two. (And if there was a row with three events, they would all get a count of three, etc.)

(2) is a little more subtle. Event #1 is obvious enough, because it can span the entire width of the calendar. Event #2 will have to shrink its width, but it can still start along the left edge. Event #3 can't.

We solve this with a per-timeslot variable I called next_hindex. It starts at 0, because by default we want to position along the left edge, but it will increase each time we find a conflict. That way, the next event (the next piece of our conflict) will start at the next horizontal position.

Step 4 is quite a bit more straightforward. The width calculation uses our max-conflict count from Step 3. If we know we have 2 events at 5:50, for example, we know each event has to be 1/2 the width of the calendar. (If we had 3 events, each would be 1/3, etc.) The x-position is calculated similarly; we're multiplying by the hindex because we want to offset by the width of (number of conflict) events.

Finally, we just create a little DOM, position our event divs, and set a random colour so they're easy to tell apart. The result is (I think) what you were looking for.

If you have any questions, I'd be happy to answer. I know this is probably more code (and more complexity) than you were expecting, but it was a surprisingly complicated problem to solve :)

Answer 4

if you want to roll your own then use following code:
DEMO: 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);
});

I strongly recommend to use http://arshaw.com/fullcalendar/
demo: http://jsfiddle.net/jGG34/2/
whatever you are trying to achieve is already implemented in this, just enable the day mode and do some css hacks.. thats it!!