会python真的可以为所欲为0(回)
353天前
这里还有人吗1(回)
538天前这里还有人吗0(回)
538天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
763天前到处都是羊，不想上班0(回)
843天前
鸽子
0(回)
847天前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; |
} |
} |
