我需要您对算法的帮助（它将在客户端使用 javascript 开发，但没关系，我最感兴趣的是算法本身）布置日历事件，以便每个事件框具有最大宽度。请看下图：
Y轴是时间。因此，如果“测试事件”在中午开始（例如）并且没有更多的相交，它会占用整个 100% 的宽度。《每周回顾》与《翻滚的基督教青年会》和《安娜/阿米莉亚》有交集，但后两者没有交集，所以都占满了 50%。Test3、Test4 和 Test5 都相交，因此每个的最大宽度为 33.3%。但是 Test7 是 66%，因为 Test3 是 33% 固定的（见上文），所以它占用了所有可用空间，即 66%。
我需要一个算法来解决这个问题。
提前致谢
/// 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;
}
编辑：现在对事件进行排序，而不是假设它们已排序。
Edit2：如果有足够的空间，现在将事件向右扩展。
接受的答案描述了一个包含 5 个步骤的算法。已接受答案的评论中链接的示例实现仅实现步骤 1 到 4。步骤 5 是关于确保最右边的事件使用所有可用空间。请参阅 OP 提供的图像中的事件 7。
我通过添加所描述算法的第 5 步来扩展给定的实现：
$( 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;
}
http://jsbin.com/detefuveta/edit?html,js,output上提供了一个工作演示。 有关扩展最右侧事件的示例，请参阅输出的第 3 列。
PS：这确实应该是对已接受答案的评论。不幸的是，我没有发表评论的特权。
这是使用 Typescript 为 React 实现的相同算法。你必须调整它以适应你的需求（当然），但它应该对任何使用 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>
);
您可以在此处查看完整的源代码。我承认这是一个自以为是的实现，但它会帮助我，所以我会在这里发布它，看看它是否对其他人有帮助！