顺序排列连续区域合并问题

假设有顺序排列的连续区域，共有两列，每列区域均顺序排序且互相之间不相交，求两列的区域交集，即：区域数列A：[2-5] [7-10] [15-25]，数列B：[4-6] [8-9] [10-20]，求出来的结果是[4-5] [8-9] [15-20]，现有一个算法是O(m+n)，请问有没有更好的效率？

算法


share
l0T0l 12 years, 4 months ago

Answers

这个算法的基础是两路归并，O(M+N)应该是理论复杂度下限了。但是还是有可能结合具体程序的前置或后置算法信息做改进，或针对输入数据的更多特殊之处做改进。如果只有这么多信息，那就只能考虑在算法复杂度的常数部分改进了。


share
跨过大海之风 answered 12 years, 4 months ago

Your Answer

Ask Question
Related questions

求一个文章和标签多对多的算法

算法：如何让小人跟着画出来的曲线上行走，已知一种

通过经纬度高效获取位置信息

求php算法，任意多个数字唯一性全排序算法

根据输入信息匹配到有缘运动员明星

比较三门解释型语言；算法和数据结构对程序员来说究竟有多重要