问题陈述
输入 n个区间组; {[s_1,t_1],[s_2,t_2],...,[s_n,t_n]}.
输出 对间隔; {[s_i,t_i],[s_j,t_j]},所有区间对中的最大重叠.
例
输入间隔:{[1,10],[2,6],[3,15],[5,9]}
- >有6个区间对.在这些对中,[1,10]和[3,15]具有最大可能的重叠7.
输出:{[1,10],[3,15]}
朴素算法将是一种强力方法,其中所有n个区间彼此进行比较,同时跟踪当前最大重叠值.对于这种情况,时间复杂度将是O(n ^ 2).
我能够找到许多关于间隔树,最大重叠间隔数和最大非重叠间隔集的程序,但没有解决这个问题.也许我能够使用上述算法中给出的想法,但我无法想出一个.
我花了很多时间试图找到一个很好的解决方案,但我认为我现在需要一些帮助.
任何建议都会有帮助!