区间覆盖问题

给定一个源区间[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;}}