区间覆盖问题

给定一个源区间[x,y](y>=x)和N个无序的目标区间[x1,y1][x2,y2]......[xn,yn],判断区间[x,y]在不在目标区间内。

 

/**
 *区间覆盖问题
 *输入：n个区间，有可能重合，还有一个区间，判断这个区间是不是与这n个区间完全重合
 *输出：true or false
 *步骤：先将n个区间按start进行排序O(nlogn)，然后根据这些区间的start和end将这些区间合并成为   *互相不相交的区间O(n)，然后判断给定区间是否与这些不相交的区间完全重叠
*/
import java.util.*;
class Interval{
	int start;
	int end;
	public Interval(int start, int end){
		this.start = start;
		this.end = end;
	}
}
public class IntervalOverlap{
	public static void main(String[] args){
		List intervalList = new ArrayList();
		Interval i1 = new Interval(2,3);
		Interval i2 = new Interval(1,2);
		Interval i3 = new Interval(3,9);
		intervalList.add(i1);
		intervalList.add(i2);
		intervalList.add(i3);

		Interval i4 = new Interval(1,6);
		System.out.println(whetherOverlap(intervalList,i4));
	}
	private static boolean whetherOverlap(List intervalList, Interval i){
		Comparator intervalComparator = new Comparator(){
			public int compare(Object o1, Object o2){
				Interval i1 = (Interval)o1;
				Interval i2 = (Interval)o2;
				return i1.start-i2.start;
			}
		};
		Collections.sort(intervalList, intervalComparator);
		for(int j=0;j<intervalList.size()-1;j++){	
			Interval i1 = (Interval)intervalList.get(j);
			Interval i2 = (Interval)intervalList.get(j+1);
			if(i1.end>=i2.start){
				i1.end = i2.end;
				intervalList.remove(j+1);
				j--;
			}
		}
		for(int j=0;j<intervalList.size();j++){
			Interval interval = (Interval)intervalList.get(j);
			if(interval.start<=i.start && interval.end >= i.end)
				return true;
		}
		return false;	
	}
}