区间覆盖有关问题
区间覆盖问题
给定一个源区间[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; } }