读书人

请教怎么在给定的多个目标区间中判断源

发布时间: 2012-03-17 19:06:28 作者: rapoo

请问如何在给定的多个目标区间中判断源区间是否包含其中?
例如:给定多个目标区间[1,2],[4,6],[3,9] 判断源区间[1,6]是否在给定的上述目标区间中。可以看出,不在。
而在给定的目标区间[1,2],[3,9],[2,3],则[1,6]包含于目标区间中。

我的大致思路是:将给定的目标区间,按照区间起始坐标排序,并对相应的区间进行合并。那么如果源区间在给定
的目标区间中的话,那么必定是某一个合并后目标区间的子区间。此时只需要顺序扫描处理后的目标区间即可。

--------------------------------------------------------------------
但是我今天在《编程之美》上看到了这个题目。书上说,在经过排序,合并预处理之后可以进行二分查找。
即在上面的例子中,可以在[1,2],[3,9],[4,6]这个有序,不相交的目标区间中,二分查找[1,6]这个区间以判断是否在
目标区间中。
我想问的是,如何进行这个二分查找过程?如果能够给出伪代码的话,感激不尽!

[解决办法]

探讨

将源区间的起始和终止端分别进行二分查找,如果两者返回值一致,则包含在目标区间中。
否则,源区间没有包含在目标区间中。
这个想法可行不?
因为经过排序和合并后的目标区间,如果过包含源区间的话,源区间必定
是某一个子目标区间的子集。

读书人网 >软件架构设计

热点推荐