区间覆盖问题

[java]代码库

package cn.rtdata.mq;

/* 
 *区间覆盖问题 
 *输入：n个区间，有可能重合，还有一个区间，判断这个区间是不是与这n个区间完全重合 
 *输出：true or false 
 *步骤：先将n个区间按start进行排序O(nlogn)，然后根据这些区间的start和end将这些区间合并成为 互相不相交的区间O(n)，然后判断给定区间是否与这些不相交的区间完全重叠 
import java.util.*;

import cn.rtdata.DataSourceManager;



public class IntervalOverlap {
    public static void main(String[] args) {
        List<Interval> intervalList = new ArrayList<Interval>();
        Interval i1 = new Interval(2, 3);
        Interval i2 = new Interval(1, 2);
        Interval i3 = new Interval(4, 9);
        Interval i5 = new Interval(11, 15);
        intervalList.add(i1);
        intervalList.add(i2);
        intervalList.add(i3);
        intervalList.add(i5);
        Interval i4 = new Interval(1, 6);
        System.out.println(whetherOverlap(intervalList, i4));
    }

    public static List<Interval> intervalMerger(List<Interval> intervalList, Interval i,boolean add){
    	if(intervalList.size()==0||add){
    		intervalList.add(i);
    		//return intervalList;
    	}
    	
        Comparator<Interval> intervalComparator = new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                long temp = o1.start-o2.start;
                if(temp==0){
                    return 0;
                }else if(temp>0){
                    return 1;
                }else{
                    return -1;
                }
            }
        };
        Collections.sort(intervalList, intervalComparator);
        for (int j = 0; j < intervalList.size() - 1; j++) {
            Interval i1 =  intervalList.get(j);
            Interval i2 =  intervalList.get(j + 1);
            if (i1.end >= i2.start-1) {
                i1.end = i2.end;
                intervalList.remove(j + 1);
                j--;
            }
        }
        
        return intervalList;
    }
/**
*区间是否在已有区间内
*/
    public static boolean whetherOverlap(List<Interval> intervalList, Interval i) {
   	if(intervalList.size()==0)
    		return false;
        intervalList = intervalMerger(intervalList,i,false);
       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;
        return true;
    }
}


package cn.rtdata.mq;

import java.io.Serializable;
/**
*区间对象
*/
public class Interval  implements Serializable{
    /**
     * 
     */
    private static final long serialVersionUID = 1L;
    long start;
    long end;

    public Interval(long start, long end) {
        this.start = start;
        this.end = end;
    }
}