求解单日Top K最高得分算法问题

给定查询数组（每个元素包含起止日期及对应区间可获得的得分）、总天数n和参数k，需要找出任意单日能获得的最高得分。计算规则为：选取当日生效的前k个最高得分求和；若k=0则取所有生效得分的总和。

示例输入：

n = 10 # 总天数
queries = [
    [1, 5, 300], # 开始日期, 结束日期, 得分
    [4, 8, 700],
    [6, 9, 100],
    [1, 2, 100],
    [2, 5, 200],
    [3, 4, 300]
]

以第4天为例：

• k=0时，总得分=300+700+200+300=1500
• k=2时，取最高两个得分求和=700+300=1000
• k=3时，取最高三个得分求和=700+300+300=1300

用户已实现基础线扫算法，但仅能计算当日所有得分总和，无法支持Top K的约束，需修改算法适配需求。

用户原有代码：

n = 10 # Number of Days
queries = [
    [1, 5, 300], # start, end, value
    [4, 8, 700],
    [6, 9, 100],
    [1, 2, 100],
    [2, 5, 200],
    [3, 4, 300]
]
def sweepline(queries,num_days,k=0):

    n = num_days
    pfx_sum = [0 for _ in range(n+1)]
    
    for st,en,val in queries:
        pfx_sum[st-1] += val
        pfx_sum[en] -= val
    
    for i in range(1,n+1):
        pfx_sum[i] += pfx_sum[i-1]

    print(max(pfx_sum))

修改后的线扫算法（支持Top K） #

方法1：使用SortedList（高效实现） #

借助sortedcontainers.SortedList实现O(log n)级别的插入、删除和切片操作，快速获取Top K元素求和：

from sortedcontainers import SortedList

n = 10  # 总天数
queries = [
    [1, 5, 300],  # 开始日期, 结束日期, 得分
    [4, 8, 700],
    [6, 9, 100],
    [1, 2, 100],
    [2, 5, 200],
    [3, 4, 300]
]

def sweepline_topk(queries, num_days, k=0):
    # 生成事件：(日期, 类型, 得分)，类型0=移除，1=添加（先处理移除事件）
    events = []
    for st, en, val in queries:
        events.append((st-1, 1, val))  # 开始日期添加得分
        events.append((en, 0, val))    # 结束日期移除得分
    
    # 排序规则：按日期升序，同日期先处理移除事件
    events.sort(key=lambda x: (x[0], x[1]))
    
    current_scores = SortedList()
    max_score = 0
    event_idx = 0
    total_events = len(events)
    
    for day in range(num_days):
        # 处理当日所有事件
        while event_idx < total_events and events[event_idx][0] == day:
            typ, val = events[event_idx][1], events[event_idx][2]
            if typ == 1:
                current_scores.add(val)
            else:
                current_scores.remove(val)
            event_idx += 1
        
        # 计算当日Top K得分总和
        if k == 0 or k >= len(current_scores):
            current_sum = sum(current_scores)
        else:
            # SortedList为升序，最后k个元素是最大的k个得分
            current_sum = sum(current_scores[-k:])
        
        if current_sum > max_score:
            max_score = current_sum
    
    print(max_score)

# 测试示例
sweepline_topk(queries, n, k=2)  # 输出1000
sweepline_topk(queries, n, k=3)  # 输出1300
sweepline_topk(queries, n, k=0)  # 输出1500

方法2：不使用第三方库（双堆+延迟删除实现） #

通过双堆结构维护生效得分集合，配合延迟删除字典处理失效元素，无需额外依赖：

import heapq

n = 10  # 总天数
queries = [
    [1, 5, 300],  # 开始日期, 结束日期, 得分
    [4, 8, 700],
    [6, 9, 100],
    [1, 2, 100],
    [2, 5, 200],
    [3, 4, 300]
]

def sweepline_topk_no_lib(queries, num_days, k=0):
    events = []
    for st, en, val in queries:
        events.append((st-1, 1, val))
        events.append((en, 0, val))
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    max_heap = []  # 大顶堆（存负值模拟），存储所有生效得分
    min_heap = []  # 小顶堆，存储当前Top K得分
    remove_counts = {}  # 延迟删除字典：记录得分待删除次数
    top_sum = 0  # 当前Top K得分总和
    max_score = 0
    event_idx = 0
    total_events = len(events)
    
    for day in range(num_days):
        # 处理当日事件
        while event_idx < total_events and events[event_idx][0] == day:
            typ, val = events[event_idx][1], events[event_idx][2]
            if typ == 1:
                heapq.heappush(max_heap, -val)
            else:
                remove_counts[val] = remove_counts.get(val, 0) + 1
            event_idx += 1
        
        # 清理大顶堆中已失效的元素
        while max_heap:
            current_val = -max_heap[0]
            if remove_counts.get(current_val, 0) > 0:
                remove_counts[current_val] -= 1
                heapq.heappop(max_heap)
            else:
                break
        
        # 补充小顶堆至Top K数量
        while max_heap and (k == 0 or len(min_heap) < k):
            val = -heapq.heappop(max_heap)
            heapq.heappush(min_heap, val)
            top_sum += val
        
        # 清理小顶堆中已失效的元素并补充新元素
        while min_heap:
            current_val = min_heap[0]
            if remove_counts.get(current_val, 0) > 0:
                remove_counts[current_val] -= 1
                top_sum -= current_val
                heapq.heappop(min_heap)
                # 从大顶堆补充有效元素
                while max_heap:
                    new_val = -max_heap[0]
                    if remove_counts.get(new_val, 0) > 0:
                        remove_counts[new_val] -= 1
                        heapq.heappop(max_heap)
                    else:
                        new_val = -heapq.heappop(max_heap)
                        heapq.heappush(min_heap, new_val)
                        top_sum += new_val
                        break
            else:
                break
        
        # 计算当日得分
        if k == 0:
            # k=0时计算所有有效得分总和
            temp_sum = top_sum
            temp_heap = max_heap.copy()
            while temp_heap:
                val = -temp_heap[0]
                if remove_counts.get(val, 0) == 0:
                    temp_sum += val
                heapq.heappop(temp_heap)
            current_sum = temp_sum
        else:
            current_sum = top_sum
        
        if current_sum > max_score:
            max_score = current_sum
    
    print(max_score)

# 测试示例
sweepline_topk_no_lib(queries, n, k=2)  # 输出1000
sweepline_topk_no_lib(queries, n, k=3)  # 输出1300
sweepline_topk_no_lib(queries, n, k=0)  # 输出1500

核心思路说明 #

1. 事件拆分与排序：将每个区间拆分为「添加得分」和「移除得分」事件，按日期排序，确保同日期先处理移除事件，避免当天结束的得分被错误计入。
2. 动态维护生效得分集合：
   • 方法1利用SortedList的有序性，快速获取最大k个元素求和，实现简洁高效。
   • 方法2通过双堆+延迟删除机制，在无第三方库的情况下实现动态Top K维护，适合环境受限场景。
3. 当日得分计算：根据k的取值，选择计算所有生效得分总和或最大k个得分总和，全程跟踪记录最大值。

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