时间戳

首页 > 解决方案 > 根据开始和结束时间对赛车手进行排名

algorithm - 根据开始和结束时间对赛车手进行排名

问题描述

问题：您有比赛的开始时间、结束时间和参赛者的索引号。你需要告诉每个赛车手的排名。排名计算如下：如果赛车手 B 在赛车手 A 之后开始但在赛车手 A 之前完成，则赛车手 A 的排名增加 1。

示例输入：

Index     Start Time     End time   
0         100            170    
1          80            150
2         120            165
3         110            145

输出：

Index     Rank
2         0
3         0
1         1
0         2

我知道我可以使用嵌套循环并对它们进行比较和排名，但仍然不能 100% 确定。有人可以帮助我在 O(n^2) 和 O(n log n) 的时间复杂度中为这个问题编写伪代码吗？提前致谢。

标签： algorithmdata-structurestime-complexitypseudocode

解决方案

Index     Start Time     End time   
0         100            170    
1          80            150
2         120            165
3         110            145

按时间升序的所有实例排序。

(80, "start", 1)
(100, "start", 0)
(110, "start", 3)
(120, "start", 2)
(145, "end", 3)
(150, "end", 1)
(165, "end", 2)
(170, "end", 0)

遍历时间列表：

80: 
current_racers = {1}

100:
current_racers = {1, 0}

110:
current_racers = {1, 0, 3}

120:
current_racers = {1, 0, 3, 2}

145:
current_racers = {1, 0, X, 2}

Racers 1 and 0 started
before racer 3 so their rank
increases by 1 when 3 is removed.

150:
current_racers = {X, 0, X, 2}
No racers started before racer
1 so no other ranks are changed
when they are removed.

165:
current_racers = {X, 0, X, X}
Racer 0 is before racer 2
so their rank is increased
when racer 2 is removed.

Ranks
0: 2
1: 1
2: 0
3: 0

在遍历期间，将竞速者插入为范围更新和点查询而安排的 fenwick 树中。（我猜“插入”只是将它们的索引记录在树中。树本身只包含与其每个索引相关的等级。）

在下一个索引处插入起始赛车手，始终在最后一次插入之前。当比赛结束时，输出存储在其索引处的排名，并将区间 [0, current_racer) 增加一。它们留在树上并不重要，因为它们不会再次影响赛车手。当树中只剩下一名赛车手时，输出他们的排名。

推荐阅读