将间隔的端点放入数组中,将其标记为起点或终点。如果间隔是封闭的,则通过将端点放在起点之前来打破平局来对它们进行排序,如果间隔是半开放的,则将它们放在相反的位置。
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
然后遍历该列表,跟踪我们处于多少间隔(这等于已处理的起点数量减去终点数量)。每当我们已经处于一个间隔中而到达起点时,这意味着我们必须具有重叠的间隔。
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E ^ ^ overlap overlap
通过将数据存储在端点旁边并跟踪我们所处的间隔,我们可以找到哪些间隔与哪些间隔重叠。
这是一个O(N logN)解决方案,其中排序是主要因素。



