/**
* 区间覆盖问题： 要求给定一组已经排好序数字，每个数字代表一个以其为起点的单位区间。
* 然后给定一个区间长度L, 要求能够覆盖到最多的单位区间，并且整个长度不超过L。
* 同时给出覆盖了哪些区间。比如L=5，{1,2,7,10,11,12,14,20,22,23}，
* 能够覆盖最多10,11,12,14四个区间，覆盖长度长度为5 <= L。
*/
#include <stdio.h>
#define M 10 //单位区间数目
#define L 5 //区间长度
int a[M] = {1,2,7,10,11,12,14,20,22,23}; //排好序的数字(单位区间)
/**
* 返回最大能够括住的区间数目，要求括住的长度不超过L
*/
int find_maxLeval(){
int begin,end;
int gap_num,gap_v;
int max_leval_num = 0;
int l,r;
//使用两个指针，分别指向括住的区间的首尾
begin = end = 0;
while(end < M){
gap_num = end - begin + 1; //括住的区间数目
gap_v = a[end] - a[begin] + 1; //括住的区间长度
if(gap_v > L){ //如果长度超过了L，则向前移动begin指针
while(gap_v > L){
begin++;
gap_num = end - begin + 1;
gap_v = a[end] - a[begin] + 1;
}
}
else{ //如果长度未超过L，则看是否需要更新括住的区间数目
if(gap_num > max_leval_num){
max_leval_num = gap_num; //更新括住的区间数目
l = begin; //更新首指针
r = end; //更新尾指针
}
}
end++;
}
printf("l=%d,r=%d\n",l,r);
return max_leval_num;
}
int main(){
int max;
max = find_maxLeval();
printf("max=%d\n",max);
return 0;
}
运行结果：
