电信套餐匹配算法超时问题求助

我自己实现了这个电信套餐匹配的算法，但部分测试用例超时了。我尝试用二分查找来优化运行效率，可还是没解决超时的问题。想请教各位大佬，我该怎么优化代码？或者是不是我的解题思路本身就有问题？万分感谢！

问题背景 #

当用户想要办理A电信的套餐时，我们需要为每个用户找出满足以下两个条件的最小编号套餐：

1. 套餐提供的流量 ≥ 用户所需流量
2. 套餐包含用户需要的所有附加服务
   如果没有符合条件的套餐，就返回0。

示例说明 #

比如有3种套餐、5类附加服务、4个用户的场景：

用户需求与匹配结果：

最终结果列表：[3,3,1,0]

输入输出示例 #

n = 5
plans = ["100 1 3", "500 4", "2000 5"]
clients = ["300 3 5", "1500 1", "100 1 3", "50 1 2"]
result = [3,3,1,0]

我的实现代码 #

def solution(n, plans, clients):
    plan_list = []
    for idx, plan in enumerate(plans):
        data, *services = map(int, plan.split())
        services.sort()
        if idx > 0:
            services = sorted(list(set(services).union(set(plan_list[idx-1][1]))))
        plan_list.append((data, services))
    
    plan_list.sort(key=lambda x: (x[0], -x[1][-1] if x[1] else 0))
    
    answer = []
    for client in clients:
        client_data, *client_services = map(int, client.split())
        client_services_set = set(client_services)
        client_services_set.discard(0)
        
        left, right = 0, len(plan_list) - 1
        selected_plan = 0
        while left <= right:
            mid = (left + right) // 2
            plan_data, plan_services = plan_list[mid]
            if plan_data >= client_data:
                if set(plan_services).issuperset(client_services_set):
                    selected_plan = mid + 1
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                left = mid + 1
        answer.append(selected_plan)
    return answer

问题分析与优化思路 #

你的解题方向是对的，但超时的核心原因在于每次判断套餐是否包含用户服务时，都要把套餐服务转成集合并调用issuperset——这一步的时间复杂度是O(k)（k是服务数量），当套餐和用户数量多、服务类型多的时候，会累积大量耗时。另外，套餐的预处理和排序逻辑也有可以优化的空间。

具体优化点 #

1. 用位掩码替代集合存储服务
   附加服务是编号形式（比如1、2、3...），我们可以用位运算来表示套餐包含的服务：服务1对应二进制的第0位（2^0），服务2对应第1位（2^1），以此类推。这样判断套餐是否包含用户所有服务，只需要做(套餐掩码 & 用户掩码) == 用户掩码，这是O(1)的操作，比集合操作快很多。

2. 简化套餐预处理逻辑
   从题目示例能看出来，后面的套餐是在前面套餐的基础上新增服务的，所以预处理时不需要每次都做集合合并和排序，直接继承前一个套餐的服务掩码，再加上当前套餐的新增服务即可，效率更高。

3. 修正套餐排序逻辑
   你当前的排序是按流量升序、服务最后一个编号降序，但我们需要的是流量升序，流量相同时套餐编号小的优先（因为要找最小编号的套餐）。预处理时保留套餐的原始编号，排序时按(流量, 原始编号)升序，这样二分查找找到的第一个满足条件的套餐就是最小编号的。

优化后的代码示例 #

def solution(n, plans, clients):
    plan_list = []
    prev_service_mask = 0
    for idx, plan in enumerate(plans):
        parts = list(map(int, plan.split()))
        data = parts[0]
        services = parts[1:]
        # 继承前一个套餐的服务，加上当前新增服务，生成掩码
        service_mask = prev_service_mask
        for s in services:
            service_mask |= (1 << (s - 1))  # 服务编号从1转成0位索引
        prev_service_mask = service_mask
        # 存储（流量，服务掩码，原始套餐编号）
        plan_list.append((data, service_mask, idx + 1))
    
    # 按流量升序，流量相同则按原始编号升序，保证小编号优先
    plan_list.sort(key=lambda x: (x[0], x[2]))
    
    answer = []
    for client in clients:
        parts = list(map(int, client.split()))
        client_data = parts[0]
        client_services = parts[1:]
        # 生成用户的服务掩码
        client_mask = 0
        for s in client_services:
            if s == 0:
                continue
            client_mask |= (1 << (s - 1))
        
        left, right = 0, len(plan_list) - 1
        selected_plan = 0
        while left <= right:
            mid = (left + right) // 2
            plan_data, plan_mask, plan_num = plan_list[mid]
            if plan_data >= client_data:
                # 位运算快速判断是否包含所有服务
                if (plan_mask & client_mask) == client_mask:
                    selected_plan = plan_num
                    right = mid - 1  # 尝试找更小编号的满足条件套餐
                else:
                    left = mid + 1
            else:
                left = mid + 1
        answer.append(selected_plan)
    return answer

优化效果说明 #

• 位运算判断服务包含关系是O(1)，相比集合的O(k)操作，在服务数量多的时候性能提升非常明显。
• 预处理时直接继承前一个套餐的掩码，避免了集合合并和排序的开销，减少了预处理时间。
• 排序时保留原始编号，确保二分查找的逻辑准确，能直接找到最小编号的满足条件套餐。

如果还有超时情况，可以考虑进一步优化：比如提前对套餐流量做前缀预处理，或者按流量分组，但上面的优化应该已经能解决大部分超时问题了。

备注：内容来源于stack exchange，提问作者jamie 8910