区间重合判断
问题描述
分析与解法
【解法一】
具体代码如下：
1 package chapter2shuzizhimei.qujianchonghe; 2 /** 3 * 区间重合判断 4 * @author DELL 5 * 6 */ 7 public class IntervalOverlap { 8 //区间类 9 public static class Interval{ 10 public double x; //区间左端点 11 public double y; //区间右端点 12 public Interval(double x, double y){ 13 this.x = x; 14 this.y = y; 15 } 16 } 17 18 //快速排序的一次划分 19 public static int partition(Interval a[], int b, int e){ 20 Interval temp = a[b]; 21 while(b<e){ 22 while(b<e&&a[e].x>=temp.x) 23 e--; 24 if(b<e) 25 a[b] = a[e]; 26 while(b<e&&a[b].x<=temp.x) 27 b++; 28 if(b<e) 29 a[e] = a[b]; 30 } 31 a[b] = temp; 32 return b; 33 } 34 35 //快速排序 36 public static void quickSort(Interval a[], int b, int e){ 37 if(b>=e) 38 return; 39 int i = partition(a, b, e); 40 quickSort(a, b, i-1); 41 quickSort(a, i+1, e); 42 } 43 44 //区间重合判断 45 public static boolean isOverlap(Interval a[], Interval b){ 46 int n = a.length, i,j; 47 quickSort(a, 0, n-1); 48 System.out.println("排序后的区间为："); 49 for(i=0;i<n;i++){ 50 System.out.println("["+a[i].x+", "+a[i].y+"] "); 51 } 52 for(i=1,j=0;i<n;i++){ 53 if(a[j].y>=a[i].x){ 54 if(a[j].y<=a[i].y){ 55 a[j].y = a[i].y; 56 } 57 } 58 else{ 59 j++; 60 a[j] = a[i]; //不能合并区间邻接存放 61 } 62 } 63 System.out.println("合并后的区间为："); 64 for(i=0;i<=j;i++){ 65 System.out.println("["+a[i].x+", "+a[i].y+"] "); 66 } 67 for(i=0;i<=j;i++){ 68 if(a[i].x<=b.x&&a[i].y>=b.y) 69 return true; 70 } 71 return false; 72 } 73 public static void main(String[] args) { 74 Interval a[] = new Interval[3]; 75 a[0] = new Interval(2,3); 76 a[1] = new Interval(1,2); 77 a[2] = new Interval(3,9); 78 Interval a1 = new Interval(1,6); 79 boolean b = isOverlap(a,a1); 80 if(b){ 81 System.out.println("区间重合！"); 82 }else{ 83 System.out.println("区间不重合！"); 84 } 85 86 } 87 88 }
程序运行结果如下：
排序后的区间为： [1.0, 2.0] [2.0, 3.0] [3.0, 9.0] 合并后的区间为： [1.0, 9.0] 区间重合！