LC 1851. 包含每个查询的最小区间

https://leetcode-cn.com/problems/minimum-interval-to-include-each-query/

这题和 LC 1847 思路几乎完全一样，我的处理方式也几乎完全一样，写了两个版本，一个是区间树，一个是题解中的事件处理方法。 和 LC 1847 不同的是，区间树的版本居然通过了，给了我比较大的信心，看来还能写代码。

区间树的 代码 依然是没有办法看，但是思路也比较清晰：

  1. 将这些区间不断地插入到区间树中。
  2. 插入区间维护好覆盖这个区间的最小size.
  3. 拿到所有的叶子节点，针对每个query进行二分。

事实证明，在做leetcode的时候如果是要写树的话，基本上思路就错了。

变为基于事件的处理方法是：

  1. 对每个interval (s, e), 产生两个事件: enter s and exit e
  2. 对每个query (q), 产生一个事件 do query on q.
  3. 在遍历事件的时候不断维护有效的区间，然后选择size最小的区间
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        events = []
        for i in range(len(intervals)):
            (a, b) = intervals[i]
            e = (a, 0, i)
            events.append(e)
            e = (b, 2, i)
            events.append(e)

        for i in range(len(queries)):
            q = queries[i]
            e = (q, 1, i)
            events.append(e)

        events.sort()
        from sortedcontainers import SortedList
        ls = SortedList()
        retired = set()
        ans = [-1] * len(queries)

        #print(events)
        for (_, type, index) in events:
            if type == 1:  # query
                while ls and ls[0][1] in retired:
                    del ls[0]
                size = -1
                if ls:
                    size = ls[0][0]
                ans[index] = size

            elif type == 0:  # enqueue.
                size = intervals[index][1] - intervals[index][0] + 1
                ls.add((size, index))

            else:
                retired.add(index)

        return ans