这是我的解决方案： # one-day A 一日日历
要求
第一部分：编写一个函数，在日历上安排一天的一系列事件。
事件将被放置在一个容器中。容器的顶部代表上午 9 点，底部代表晚上 9 点。
容器的宽度为 620 像素（左右填充 10 像素），高度为 720 像素（上午 9 点到晚上 9 点之间每分钟 1 个像素）。对象的布局应使它们在视觉上不会重叠。如果给定时间段只有一个事件，则其宽度应为 600 像素。
有两个主要限制： 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
]
除了 id、开始和结束时间之外，该函数还应返回一个事件对象数组，这些对象对象设置了 left 和 top 位置（相对于容器的左上角）。
第 II 部分：使用第 I 部分中的函数创建一个样式类似于下面示例图像的网页。
带有以下日历事件：
- 上午 9:30 开始，上午 11:30 结束的活动
- 下午 6:00 开始，晚上 7:00 结束的活动
- 下午 6:20 开始，晚上 7:20 结束的活动
- 晚上 7:10 开始，晚上 8:10 结束的活动
代码
安装和运行
- 克隆这个 repo
- 在您喜欢的浏览器中打开 index.html 文件。
注意：在启动时有一组默认事件（第二部分需要）。
为了测试，在默认数组的正下方（第 14 行），您可以找到generateEvents生成随机事件数组的函数。数组大小将由 arrayLength 属性确定。
依赖项
没有任何！
解决方案
您可以在下面找到根据要求解决问题的算法。
介绍
我将尝试用图表的方式来解决这个任务，所以应该给出很少的术语。
条款
节点：代表一个事件 - $n$, $n \in N, N$ - 所有节点的组。
边：表示碰撞事件 - $e$, $e \in E, E$ - 所有边的组。例如，如果节点 $u$ 和 $v$ 发生碰撞，那么将有一条边 $e_{u,v}$ 连接它们。
图：节点和边 $G, G\in(N,E)$ 的集合。
Cluster：表示一组连接的节点（图的子组） - $c$, $c \subseteq G$。例如，如果我们有以下节点：$u, v, w$ 和边 $e_{u,v}$。然后会有 2 个簇，第一个包含 $u,v$，第二个只包含 $w$。
集团：表示集群中节点的子组，该组中的每一对节点都有一条连接边 - $cq$, $cq \subseteq c$。注意，一个 clique 代表一组碰撞事件。
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}
]
该图将是：
黑色循环 - 节点 - 事件
绿色椭圆 - 集团 - 碰撞事件组
红色椭圆 - 集群 - 连接节点组
蓝色线 - 边缘 - 碰撞事件之间的连接器
注意：左上角的绿色椭圆是左侧集群中最大的集团。
董事会将是：
红色矩形 - 簇
彩色圆点 - 派系（每种颜色都是不同的派系）。
约束释义
- 同一集群中的每个节点必须在板上具有相同的宽度，以满足第一个约束。
- 节点不得在板上相互重叠，同时淀粉至最大宽度并仍遵守第一个约束。
- 集群中节点的宽度将由集群中最大的集团设置。这是真的，因为同一集团中的节点将在棋盘上共享至少一分钟，这意味着它们必须具有相同的宽度（因为它们正在碰撞）。因此集群中的其他节点将具有与最小节点相同的宽度。
- clique 中的每个节点都将获得其相对于其邻居的 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代表在这一分钟发生的一个事件。
伪代码：
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]
]
第二步：创建图
在这一步中，将创建图，包括节点、节点邻居和集群，还将确定集群的最大集团。
请注意，不会有边缘实体，每个节点都将保存一个节点映射（键：节点 ID，值：节点），它与（其邻居）发生冲突。这张地图将被称为邻居。此外，maxCliqueSize将向每个节点添加一个属性。maxCliqueSize是该节点所属的最大集团。
伪代码：
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];
}
}
}
}
第三步：计算每个簇的宽度。
如上所述，集群中所有节点的宽度将由集群中最大集团的大小决定。
集群 $c$ 中每个节点 $n$ 的宽度将遵循以下等式：
$$n_{width} = \frac{Board_{width}}{Max\left (n_{1}.biggestCliqueSize, n_{2}。最大CliqueSize, ..., n_{n}.biggestCliqueSize\right )}$$
每个节点宽度都将在与其相关的集群中设置。因此将在集群实体上设置宽度属性。
伪代码：
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 轴位置。集群中最大的集团将决定可用名额的数量。
伪代码：
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;
}
}
}
第五步：将节点放在板上。在这一步中，我们已经拥有了将事件（节点）放置在板上的位置所需的所有信息。每个节点的位置和大小将由以下因素决定：
- 高度：node.end - node.start
- 宽度：node.cluster.width
- 顶部偏移：node.start
- 左偏移：node.cluster.width * node.position + 左填充
算法复杂度
该算法的时间复杂度为$O\left(n^{2}\right)$。
该算法的空间复杂度为$O\left (n\right)$。
Github 仓库：https ://github.com/vlio20/one-day
