最大重叠区间个数

问题： 给定多个可能重叠的区间，找出重叠区间的个数的最大值。区间定义如下：

public class Interval{int start; //起点int end; //止点Interval(int a,int b){start=a;end=b;}
}

思路： 将区间边界转换成点，对所有点进行排序，扫描排序结果。当遇到起点时，重叠个数加一，并且记录重叠个数的最大值；当遇到止点时，重叠个数减一。

java代码：

class Point implements Comparable<Point>{int value;int type;Point(int v,int t){value=v;type=t;}public int compareTo(Point p){if(this.value==p.value){return 0;}else if(this.value>p.value){return 1;}else{return -1;}}
}int getOverlappingCount(Interval[] A){int max=0,count=1;if(A==null||A.length==0)return max;Point[] points=new Point[A.length*2];for(int i=0;i<A.length;i++){points[2*i]=new Point(A[i].start,0);points[2*i+1]=new Point(A[i].end,1);}Collections.sort(points);for(int i=0;i<points.length;i++){if(points[i].type==0){count++;max=Math.max(max,count);}else{count--;}}return max;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！