一、问题
给定一个源区间[x,y](y>=x)和N个无序的目标区间[x1,y1],[x2,y2],...,[xn,yn]，判断源区间[x,y]是不是在目标区间内。
例：
给定源区间[1 6]和一组无须的目标区间[2 3][1 2][3 9]，即可认为区间[1 6]在区间[2 3][1 2][3 9]内（因为目标区间实际上时[1,9]）。
问题分析：
输入：源区间[x,y]，可以用一个长度为2的数组表示；N个无序的目标区间[x1,y1],[x2,y2],...,[xn,yn]，可用为长度为N，子数组长度为2的二维数组表示。
输出：1值表示源区间[x,y]在目标区间内，0值表示源区间[x,y]不在目标区间内。
约束：为简化分析，这里表示区间的均是整数值，实际上可以考虑浮点表示；输入的所有区间[xi,yi]有xi <= yi。
二、解法
解法一 遍历合并（自我思考实现）
思考：虽然问题中含有表示区间的含义[xi,yi]，但这里输入的所有的数据量为(N + 1) * 2。判断源区间是否在目标区间内，我们可以先对目标区间进行处理，将N个目标区间处理为n(n <= N)个区间（合并），处理后的区间有如下特点：两两交集均为零。接下来通过逐一判断源区间[x,y]是否在这些处理后的n个区间内即可知道源区间是否在目标区间内。
我们现在考虑如何将N个目标区间处理为n(n <= N)个区间（两两交集均为空集）。考虑到区间可能时大于两个的目标区间的并集，我们采用分治或递归的想法，不断进行两两有重合的区间求并集，直到任意两个区间间交集均为0。任意两个区间之间是否重叠，如[x1,y1]和[x2,y2]，通过判断x1,x2,y1,y2之间的大小关系即可。
时间复杂度：嵌套遍历处理目标区间时间复杂度为O(n^2)，判断源区间是否在这些区间内时间复杂度为O(n)，算法总时间复杂度为O(n^2)。
算法C实现：
设置标志位0和1分别表示处理后留下来的区间和丢弃的区间（当两个区间有重叠时修改前一个区间使之为这两个区间的并集，同时丢弃后一个区间）。
采用嵌套遍历，使得遍历后留下来的区间为对N个目标区间进行处理后的n个区间，并满足两两交集为空集。
/**
* @file range_overlap_judgement.c
* @brief judge if the given source range is in the given target ranges.
* @author chenxilinsidney@gmail.com
* @version 1.0
* @date 2015-02-03
*/
#include <stdlib.h>
#include <stdio.h>
// #define NDEBUG
#include <assert.h>
#include "memory.h"
// #define NDBG_PRINT
#include "debug_print.h"
typedef int TYPE;
#define MAX_COUNT 10
TYPE array[MAX_COUNT][2] = {{0}};
/**
* @brief judge if the given source range is in the given target ranges.
*
* @param[in] source source range array length 2
* @param[in] target target range, each range has two values
* @param[in] count target range count
*
* @return return 1 if the given source range is in the given target ranges,
* others return 0.
*/
TYPE range_overlap_judgement(TYPE* source, TYPE* target, TYPE count)
{
// x <= y for range [x, y]
assert(source[0] <= source[1]);
TYPE i, j;
for (i = 0; i < count; i++) {
assert(target[i << 1] <= target[(i << 1) + 1]);
}
// target range combined
TYPE *x1, *y1, *x2, *y2;
TYPE* flag_targe_done = SCALLOC(count, TYPE);
/// get first range
for (i = 0; i < count; i++) {
if (flag_targe_done[i])
continue;
x1 = target + (i << 1);
y1 = target + (i << 1) + 1;
/// do with the second range
for (j = i + 1; j < count; j++) {
if (flag_targe_done[j])
continue;
x2 = target + (j << 1);
y2 = target + (j << 1) + 1;
/// process two relative range
if (*x2 >= *x1 && *x2 <= *y1) {
if (y1 <= y2) {
/// refresh range
*y1 = *y2;
}
flag_targe_done[j] = 1;
} else if (*y2 >= *x1 && *y2 <= *y1) {
if (*x2 <= *x1) {
/// refresh range
*x1 = *x2;
}
flag_targe_done[j] = 1;
} else if(*x2 <= *x1 && *y1 <= *y2) {
/// refresh range
*x1 = *x2;
*y1 = *y2;
flag_targe_done[j] = 1;
}
}
}
// display the processed range
DEBUG_PRINT_STRING("test flag and range.\n");
for (i = 0; i < count; i++) {
/// ignore useless range
if (!flag_targe_done[i]) {
DEBUG_PRINT_VALUE("%d", target[i << 1]);
DEBUG_PRINT_VALUE("%d", target[(i << 1) + 1]);
}
}
// source range detect
DEBUG_PRINT_STRING("test source range.\n");
for (i = 0; i < count; i++) {
/// ignore useless range and test if source range in the target range
if (!flag_targe_done[i] && target[i << 1] <= source[0] &&
target[(i << 1) + 1] >= source[1]) {
SFREE(&flag_targe_done);
return 1;
}
}
SFREE(&flag_targe_done);
return 0;
}
int main(void) {
/// read range to array, each range write as [32,24]
TYPE count = 0;
while(count < MAX_COUNT && scanf("[%d,%d]\n",
*(array + count), *(array + count) + 1) == 2) {
++count;
}
/// make last range as source range
TYPE source[2] = {0};
count--;
source[0] = array[count][0];
source[1] = array[count][1];
printf("the source range(ex:3 5) is [%d,%d]\n",source[0], source[1]);
printf("the target range count = %d\n", count);
/// output result
if(range_overlap_judgement(source, (TYPE*)array, count)) {
printf("The source range is in the target range.\n");
} else {
printf("The source range is not in the target range.\n");
}
return EXIT_SUCCESS;
}
解法二 （参考 《编程之美》）
解法一可以改善的地方是合并目标区间的算法，解法一采用的是嵌套遍历，时间复杂度是O(n^2)。解法二采用另一种和并目标区间的算法，思路如下：首先利用区间的左值边界先对区间进行快速排序O(n*lgn)，再进行合并O(n)。这样接下来可以使用二分查找进行查找(单次查找O(lgn))并判断源区间是否在目标区间内，(思路一如下：分别查找源区间的两个边界处于排序合并后的哪个区间，再判断这两个区间是否为同一个区间，若为同一个，则说明源区间在目标区间内；思路二如下：查找源区间的一个边界处于排序后并后哪个区间，再判断另一个边界是否位于此区间内）。这种算法总的时间复杂度为O(n*lgn
+ n + k*lgn)(k为查找次数)。不仅总的时间复杂度减低了，还有一个优点就是：若给定多个源区间(k >> n)，则判定每个源区间是否在目标区间内仅需O(lgn)时间，大大加快来查找的速度(解法一需O(n)时间)。
分析：尽管N个目标区间均采用两个数而不是一个数来表示，但是仍然可以利用快速排序和二分查找算法对这些数据进行处理，稍微变换下排序思路和查找思路即可，可见排序查找的应用是相当广泛的，并不局限一个单个数据，可以拓展到其他类型。