请教一道数组题，求最优方案或者 leetcode 类似题目

x = range(1, 2000)
y = [range(125, 200), range(200, 400), range(300, 500)...]
y 里面每个 interval 的取值范围都在 x 中，求 y 中出现次数最多的数。如果答案是多个数，比如 range(200,300), 任何一个都行。


y 的数量非常大，希望找到 time, space 上的最优化算法
不能用两个循环，时间太大不接受。

也不能 flatten y，空间太大不接受。

求指点最优方案 and/or leetcode 上类似题目

Leetcode #253 很类似 https://leetcode.com/problems/meeting-rooms-ii/
但是，这个是付费会员才能看到的题目

题目是很多的meeting 时间 range，问你最少需要多少个meeting room。 其实就是问重复出现的时间点最多出现了多少次。
而你的题目相当于问重复出现次数最多的时间点，给出一个例子来。略有不同

原题这样可以这样解：

from typing import List
from itertools import accumulate


class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        arr = [d for _, d in sorted(
            x for s, e in intervals for x in ((s, 1), (e, -1)))]
        return max(accumulate(arr))


solution = Solution()
print(solution.minMeetingRooms([[0, 30], [5, 10], [15, 20]]))  # 2
print(solution.minMeetingRooms([[7, 10], [2, 4]]))  # 1

可以写成一行：
return max(accumulate(d for _, d in sorted(x for s, e in intervals for x in ((s, 1), (e, -1)))))

你需要调整下才能适配到你的问题。只能帮到这了，很多天没刷题了。

byt2015 发表于 2023-05-18 14:49:11
没太看懂 arr presum 最大那一步，如果 arr =，怎么找到最大值？
这个算法为什么可行？有什么关键字或者常见题目吗？想搜索学习下。

可以看这个: https://leetcode.com/problems/ma...eep-Line-algorithm/

楼上说的基本是对的，另外如果x范围很大，注意要离散化排序一下端点

扫描线，开一个长度为x的arr，y从左扫到右，每个interval左端点在arr上+1，右端点-1，最后在arr上取最大值

Actuant 发表于 2023-5-18 17:22
扫描线，开一个长度为x的arr，y从左扫到右，每个interval左端点在arr上+1，右端点-1，最后在arr上取最大值

只在端点做加减？
arr = [0]* len(x)

for begin, end in interval:
arr[begin]+=1
arr[end]-=1

取 max(arr)?

byt2015 发表于 2023-05-18 13:04:43
只在端点做加减？
arr = * len(x)

最后一步不能直接max，要keep一个presum找最大

举例: x=[0,5), y=[[0,4),[1,4),[2,5)], 那么arr=[1,1,1,0,-2,-1], presum最大值3在[2,4)能取到。加减的地方可能要offset 1取决于开闭区间

变种meeting room。把meeting room的题全做一遍就能手写了

Actuant 发表于 2023-5-18 17:41
最后一步不能直接max，要keep一个presum找最大

举例: x=[0,5), y=[[0,4),[1,4),[2,5)], 那么arr=[1,1,1,0 ...

没太看懂 arr presum 最大那一步，如果 arr =[1,0,1,-1,0,2,0,-2]，怎么找到最大值？
这个算法为什么可行？有什么关键字或者常见题目吗？想搜索学习下。

离散化差分