线性时间求出能够覆盖的最多区间数目

/**
* 区间覆盖问题： 要求给定一组已经排好序数字，每个数字代表一个以其为起点的单位区间。
* 然后给定一个区间长度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;
}

运行结果：