Visualization of calendar events. Algorithm for composing events with maximum width

Question

I need your help with an algorithm (it will be developed on the client side using javascript, but it doesn’t really matter much, I'm most interested in the algorithm itself), postponing calendar events so that each event field has the maximum width, Please view the following image:

Y axis is time. Therefore, if a “test event” begins at noon (for example) and no longer intersects with it, it occupies the entire 100% width. The Weekly Review overlaps with Tumbling YMCA and Anna / Amelia, but the last two do not overlap, so they all fill 50%. Test3, Test4 and Test5 all intersect, so the maximum width is 33.3% for each. But Test7 is 66%, because Test3 is fixed at 33% (see above), so it takes up all the free space, which is 66%.

I need an algorithm how to make it.

Thank you in advance

Answer 1

• Think of an unlimited grid with a left edge.
• Each event has a width of one cell, and the height and vertical position are fixed depending on the start and end times.
• Try to place each event in a column as far as possible, without crossing any earlier events in that column.
• Then, when each related group of events is placed, their actual width will be 1 / n of the maximum number of columns used by the group.
• You can also expand events in the left and right places to use the remaining space.

/// Pick the left and right positions of each event, such that there are no overlap. /// Step 3 in the algorithm. void LayoutEvents(IEnumerable<Event> events) { var columns = new List<List<Event>>(); DateTime? lastEventEnding = null; foreach (var ev in events.OrderBy(ev => ev.Start).ThenBy(ev => ev.End)) { if (ev.Start >= lastEventEnding) { PackEvents(columns); columns.Clear(); lastEventEnding = null; } bool placed = false; foreach (var col in columns) { if (!col.Last().CollidesWith(ev)) { col.Add(ev); placed = true; break; } } if (!placed) { columns.Add(new List<Event> { ev }); } if (lastEventEnding == null || ev.End > lastEventEnding.Value) { lastEventEnding = ev.End; } } if (columns.Count > 0) { PackEvents(columns); } } /// Set the left and right positions for each event in the connected group. /// Step 4 in the algorithm. void PackEvents(List<List<Event>> columns) { float numColumns = columns.Count; int iColumn = 0; foreach (var col in columns) { foreach (var ev in col) { int colSpan = ExpandEvent(ev, iColumn, columns); ev.Left = iColumn / numColumns; ev.Right = (iColumn + colSpan) / numColumns; } iColumn++; } } /// Checks how many columns the event can expand into, without colliding with /// other events. /// Step 5 in the algorithm. int ExpandEvent(Event ev, int iColumn, List<List<Event>> columns) { int colSpan = 1; foreach (var col in columns.Skip(iColumn + 1)) { foreach (var ev1 in col) { if (ev1.CollidesWith(ev)) { return colSpan; } } colSpan++; } return colSpan; } 

Edit: Now sorts events, rather than assuming they are sorted.

Edit2: Now the event expands to the right if there is enough space.

Answer 2

The accepted answer describes an algorithm with 5 steps. An implementation example, linked in the comments of the accepted answer, implements only steps 1 to 4. Step 5 is to make sure that the right-most event uses all the free space. See Event 7 in the image provided by the OP.

I expanded this implementation by adding step 5 of the described algorithm:

 $( document ).ready( function( ) { var column_index = 0; $( '#timesheet-events .daysheet-container' ).each( function() { var block_width = $(this).width(); var columns = []; var lastEventEnding = null; // Create an array of all events var events = $('.bubble_selector', this).map(function(index, o) { o = $(o); var top = o.offset().top; return { 'obj': o, 'top': top, 'bottom': top + o.height() }; }).get(); // Sort it by starting time, and then by ending time. events = events.sort(function(e1,e2) { if (e1.top < e2.top) return -1; if (e1.top > e2.top) return 1; if (e1.bottom < e2.bottom) return -1; if (e1.bottom > e2.bottom) return 1; return 0; }); // Iterate over the sorted array $(events).each(function(index, e) { // Check if a new event group needs to be started if (lastEventEnding !== null && e.top >= lastEventEnding) { // The latest event is later than any of the event in the // current group. There is no overlap. Output the current // event group and start a new event group. PackEvents( columns, block_width ); columns = []; // This starts new event group. lastEventEnding = null; } // Try to place the event inside the existing columns var placed = false; for (var i = 0; i < columns.length; i++) { var col = columns[ i ]; if (!collidesWith( col[col.length-1], e ) ) { col.push(e); placed = true; break; } } // It was not possible to place the event. Add a new column // for the current event group. if (!placed) { columns.push([e]); } // Remember the latest event end time of the current group. // This is later used to determine if a new groups starts. if (lastEventEnding === null || e.bottom > lastEventEnding) { lastEventEnding = e.bottom; } }); if (columns.length > 0) { PackEvents( columns, block_width ); } }); }); // Function does the layout for a group of events. function PackEvents( columns, block_width ) { var n = columns.length; for (var i = 0; i < n; i++) { var col = columns[ i ]; for (var j = 0; j < col.length; j++) { var bubble = col[j]; var colSpan = ExpandEvent(bubble, i, columns); bubble.obj.css( 'left', (i / n)*100 + '%' ); bubble.obj.css( 'width', block_width * colSpan / n - 1 ); } } } // Check if two events collide. function collidesWith( a, b ) { return a.bottom > b.top && a.top < b.bottom; } // Expand events at the far right to use up any remaining space. // Checks how many columns the event can expand into, without // colliding with other events. Step 5 in the algorithm. function ExpandEvent(ev, iColumn, columns) { var colSpan = 1; // To see the output without event expansion, uncomment // the line below. Watch column 3 in the output. //return colSpan; for (var i = iColumn + 1; i < columns.length; i++) { var col = columns[i]; for (var j = 0; j < col.length; j++) { var ev1 = col[j]; if (collidesWith(ev, ev1)) { return colSpan; } } colSpan++; } return colSpan; } 

A working demo is available at http://jsbin.com/detefuveta/edit?html,js,output See Output Column 3 for examples of extending the right-most events.

PS: This should be a comment on the accepted answer. Unfortunately, I do not have privileges to comment.