基于竞速者起止时间计算排名的O(n²)与O(nlogn)伪代码实现

规则重述 #

每名竞速者的排名值等于满足以下条件的其他竞速者B的数量：B的开始时间晚于当前竞速者，且B的结束时间早于当前竞速者。排名值越小排名越靠前。

O(n²) 时间复杂度实现 #

核心思路是暴力枚举所有两两竞速者组合，逐个判断是否满足排名值累加条件，逻辑简单直接，适合数据量较小的场景。

输入: racers数组，每个元素包含属性 index(编号), start(开始时间), end(结束时间)
n = racers.length
// 初始化所有竞速者的排名值为0
rank = [0 for i in 0..n-1]

// 外层遍历每个作为计数对象的竞速者A
for i from 0 to n-1:
    A = racers[i]
    // 内层遍历所有其他竞速者B，判断是否给A的排名值+1
    for j from 0 to n-1:
        if i == j:
            continue
        B = racers[j]
        if B.start > A.start and B.end < A.end:
            rank[i] = rank[i] + 1

// 按排名值升序排序，输出结果
output_list = 组合(racers的index, rank)，按rank升序排列
打印 output_list

O(n log n) 时间复杂度实现 #

核心思路是通过排序消除单维度的判断成本，配合树状数组（Fenwick Tree）快速统计符合条件的元素数量，适合数据量较大的场景。

实现逻辑说明 #

1. 先将所有竞速者按开始时间降序排序，这样遍历的时候，所有已经处理过的竞速者的开始时间都大于当前竞速者，只需要判断结束时间维度的条件即可
2. 对所有结束时间做离散化处理，避免结束时间数值过大导致树状数组空间浪费
3. 遍历排序后的竞速者，每次查询树状数组中小于当前竞速者结束时间的元素总数，即为当前竞速者的排名值，再将当前结束时间插入树状数组

输入: racers数组，每个元素包含属性 index(编号), start(开始时间), end(结束时间)
n = racers.length
rank = [0 for i in 0..n-1]

// 步骤1：离散化结束时间，映射为小范围整数
all_ends = [r.end for r in racers]
sorted_unique_ends = 排序并去重(all_ends)
// 映射函数：输入end值，返回对应的离散化序号（从1开始，适配树状数组索引要求）
function get_end_rank(e):
    return 二分查找(sorted_unique_ends, e) + 1
max_end_rank = sorted_unique_ends.length

// 步骤2：按start降序排序竞速者，start相同顺序不影响
sorted_racers = 排序(racers, 排序规则: 按start降序)

// 步骤3：初始化树状数组，支持单点更新、前缀和查询
ft = FenwickTree(size = max_end_rank)

// 步骤4：遍历计算每个竞速者的排名值
for each racer in sorted_racers:
    current_end_rank = get_end_rank(racer.end)
    // 查询小于当前end的元素总数，即排名值
    count = ft.query(current_end_rank - 1)
    rank[racer.index] = count
    // 把当前end插入树状数组
    ft.update(current_end_rank, 1)

// 按排名值升序排序，输出结果
output_list = 组合(所有racer的index, rank)，按rank升序排列
打印 output_list

树状数组基础操作伪代码参考 #

class FenwickTree:
    function __init__(size):
        this.tree = [0 for i in 0..size]
    
    // 单点更新：给索引idx位置的值加delta
    function update(idx, delta):
        while idx < length(this.tree):
            this.tree[idx] += delta
            idx += idx & -idx
    
    // 前缀和查询：查询1~idx的元素总和
    function query(idx):
        res = 0
        while idx > 0:
            res += this.tree[idx]
            idx -= idx & -idx
        return res

内容的提问来源于stack exchange，提问作者user16782109