Visualization of calendar events. Algorithm to layout events with maximum width

I need your help with an algorithm (it will be developed on client side with javascript, but doesn't really matter, I'm mostly interested in the algorithm itself) laying out calendar events so that each event box has maximum width. Please see the following picture:

Y axis is time. So if "Test event" starts at noon (for example) and nothing more intersects with it, it takes the whole 100% width. "Weekly review" intersects with "Tumbling YMCA" and "Anna/Amelia", but the latter two are not intersecting, so they all fill up 50%. Test3, Test4 and Test5 are all intersecting, so max width is 33.3% for each. But Test7 is 66% since Test3 is 33% fixed (see above) , so it takes all available space , which is 66%.

I need an algorithm how to lay this out.

Thanks in advance

Solution 1:

1. Think of an unlimited grid with just a left edge.
2. Each event is one cell wide, and the height and vertical position is fixed based on starting and ending times.
3. Try to place each event in a column as far left as possible, without it intersecting any earlier event in that column.
4. Then, when each connected group of events is placed, their actual widths will be 1/n of the maximum number of columns used by the group.
5. You could also expand the events at the far left and right to use up any 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 the events, instead of assuming they is sorted.

Edit2: Now expands the events to the right, if there are enough space.

Solution 2:

The accepted answer describes an algorithm with 5 steps. The example implementation linked in the comments of the accepted answer implements only steps 1 to 4. Step 5 is about making sure the rightmost event uses all the space available. See event 7 in the image provided by the OP.

I expanded the given 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 column 3 of the output for examples of expanding the rightmost events.

PS: This should really be a comment to the accepted answer. Unfortunately I don't have the privileges to comment.

Solution 3:

Here's the same algorithm implemented for React using Typescript. You'll have to tweak it to fit your needs (of course), but it should prove useful for anyone working in React:

// Place concurrent meetings side-by-side (like GCal).
// @see {@link https://share.clickup.com/t/h/hpxh7u/WQO1OW4DQN0SIZD}
// @see {@link https://stackoverflow.com/a/11323909/10023158}
// @see {@link https://jsbin.com/detefuveta/edit}

// Check if two events collide (i.e. overlap).
function collides(a: Timeslot, b: Timeslot): boolean {
  return a.to > b.from && a.from < b.to;
}

// Expands events at the far right to use up any remaining
// space. Returns the number of columns the event can
// expand into, without colliding with other events.
function expand(
  e: Meeting,
  colIdx: number,
  cols: Meeting[][]
): number {
  let colSpan = 1;
  cols.slice(colIdx + 1).some((col) => {
    if (col.some((evt) => collides(e.time, evt.time)))
      return true;
    colSpan += 1;
    return false;
  });
  return colSpan;
}

// Each group contains columns of events that overlap.
const groups: Meeting[][][] = [];
// Each column contains events that do not overlap.
let columns: Meeting[][] = [];
let lastEventEnding: Date | undefined;
// Place each event into a column within an event group.
meetings
  .filter((m) => m.time.from.getDay() === day)
  .sort(({ time: e1 }, { time: e2 }) => {
    if (e1.from < e2.from) return -1;
    if (e1.from > e2.from) return 1;
    if (e1.to < e2.to) return -1;
    if (e1.to > e2.to) return 1;
    return 0;
  })
  .forEach((e) => {
    // Check if a new event group needs to be started.
    if (
      lastEventEnding &&
      e.time.from >= lastEventEnding
    ) {
      // The event is later than any of the events in the
      // current group. There is no overlap. Output the
      // current event group and start a new one.
      groups.push(columns);
      columns = [];
      lastEventEnding = undefined;
    }

    // Try to place the event inside an existing column.
    let placed = false;
    columns.some((col) => {
      if (!collides(col[col.length - 1].time, e.time)) {
        col.push(e);
        placed = true;
      }
      return placed;
    });

    // It was not possible to place the event (it overlaps
    // with events in each existing column). Add a new column
    // to the current event group with the event in it.
    if (!placed) columns.push([e]);

    // Remember the last event end time of the current group.
    if (!lastEventEnding || e.time.to > lastEventEnding)
      lastEventEnding = e.time.to;
  });
groups.push(columns);

// Show current time indicator if today is current date.
const date = getDateWithDay(day, startingDate);
const today =
  now.getFullYear() === date.getFullYear() &&
  now.getMonth() === date.getMonth() &&
  now.getDate() === date.getDate();
const { y: top } = getPosition(now);

return (
  <div
    key={nanoid()}
    className={styles.cell}
    ref={cellRef}
  >
    {today && (
      <div style={{ top }} className={styles.indicator}>
        <div className={styles.dot} />
        <div className={styles.line} />
      </div>
    )}
    {groups.map((cols: Meeting[][]) =>
      cols.map((col: Meeting[], colIdx) =>
        col.map((e: Meeting) => (
          <MeetingItem
            now={now}
            meeting={e}
            viewing={viewing}
            setViewing={setViewing}
            editing={editing}
            setEditing={setEditing}
            setEditRndVisible={setEditRndVisible}
            widthPercent={
              expand(e, colIdx, cols) / cols.length
            }
            leftPercent={colIdx / cols.length}
            key={e.id}
          />
        ))
      )
    )}
  </div>
);

You can see the full source-code here. I'll admit that this is a highly opinionated implementation, but it would've helped me so I'll post it here to see if it helps anyone else!