在日程安排或预约排期等场景中,经常会需要对比2个或多个时间段是重叠的功能,我经过整理和验证,发现了下面的算法比较好一些,分享一下。
1.只有2个时间段的情况
例如:存在区间A、区间B,重叠的情况很多,但不重叠的情况只有2种,A在B前或者B在A前。如图:
得出,不重叠算法:A.end< B.start || A.start > B.end
那么重叠的算法对上面取反就可以了:! (A.end< B.start || A.start > B.end)
Java算法实现:! (A.end< B.start || A.start > B.end) 这里为了通用性,将时间类统一通过getTime()方法,转换为时间戳对比。
/**
* 判断2个时间段是否有重叠(交集)
* @param startDate1 时间段1开始时间戳
* @param endDate1 时间段1结束时间戳
* @param startDate2 时间段2开始时间戳
* @param endDate2 时间段2结束时间戳
* @param isStrict 是否严格重叠,true 严格,没有任何相交或相等;false 不严格,可以首尾相等,比如2021/5/29-2021/5/31和2021/5/31-2021/6/1,不重叠。
* @return 返回是否重叠
*/
public static boolean isOverlap(long startDate1, long endDate1, long startDate2, long endDate2, boolean isStrict){
if(endDate1<startDate1){
throw new DateTimeException("endDate1不能小于startDate1");
}
if(endDate2<startDate2){
throw new DateTimeException("endDate2不能小于startDate2");
}
if(isStrict){
if(! (endDate1<startDate2 || startDate1>endDate2)){
return true;
}
}else{
if(! (endDate1<=startDate2 || startDate1>=endDate2)){
return true;
}
}
return false;
}
/**
* 判断2个时间段是否有重叠(交集)
* @param startDate1 时间段1开始时间
* @param endDate1 时间段1结束时间
* @param startDate2 时间段2开始时间
* @param endDate2 时间段2结束时间
* @param isStrict 是否严格重叠,true 严格,没有任何相交或相等;false 不严格,可以首尾相等,比如2021-05-29到2021-05-31和2021-05-31到2021-06-01,不重叠。
* @return 返回是否重叠
*/
public static boolean isOverlap(Date startDate1, Date endDate1, Date startDate2, Date endDate2, boolean isStrict){
Objects.requireNonNull(startDate1, "startDate1");
Objects.requireNonNull(endDate1, "endDate1");
Objects.requireNonNull(startDate2, "startDate2");
Objects.requireNonNull(endDate2, "endDate2");
return isOverlap(startDate1.getTime(), endDate1.getTime(), startDate2.getTime(), endDate2.getTime(), isStrict);
}
复制代码
2.大于2个时间段的情况
如果大于2个时间段,需要相互都比较一次,比较麻烦,可以先根据开始时间排序,然后一次遍历对比:
由上面2个时间段算法得出,有序情况下,不重叠算法:A.end< B.start
那么重叠的算法对上面取反就可以了:! (A.end< B.start)
Java算法实现:先根据开始时间排序,遍历对比,! (A.end< B.start)
/**
- 时间段
*@author xkzhangsan
*/
public class TimePair {
public TimePair(long start, long end) {
if(end<start){
throw new DateTimeException("end不能小于start");
}
this.start = start;
this.end = end;
}
private long start;
private long end;
public long getStart() {
return start;
}
public void setStart(long start) {
this.start = start;
}
public long getEnd() {
return end;
}
public void setEnd(long end) {
this.end = end;
}
复制代码
}
/**
* 判断多个时间段是否有重叠(交集)
* @param timePairs 时间段数组
* @param isStrict 是否严格重叠,true 严格,没有任何相交或相等;false 不严格,可以首尾相等,比如2021-05-29到2021-05-31和2021-05-31到2021-06-01,不重叠。
* @return 返回是否重叠
*/
public static boolean isOverlap(TimePair[] timePairs, boolean isStrict){
if(timePairs==null || timePairs.length==0){
throw new DateTimeException("timePairs不能为空");
}
Arrays.sort(timePairs, Comparator.comparingLong(TimePair::getStart));
for(int i=1;i<timePairs.length;i++){
if(isStrict){
if(! (timePairs[i-1].getEnd()<timePairs[i].getStart())){
return true;
}
}else{
if(! (timePairs[i-1].getEnd()<=timePairs[i].getStart())){
return true;
}
}
}
return false;
}
/**
* 判断多个时间段是否有重叠(交集)
* @param timePairList 时间段列表
* @param isStrict 是否严格重叠,true 严格,没有任何相交或相等;false 不严格,可以首尾相等,比如2021-05-29到2021-05-31和2021-05-31到2021-06-01,不重叠。
* @return 返回是否重叠
*/
public static boolean isOverlap(List<TimePair> timePairList, boolean isStrict){
if(CollectionUtil.isEmpty(timePairList)){
throw new DateTimeException("timePairList不能为空");
}
TimePair[] timePairs = new TimePair[timePairList.size()];
timePairList.toArray(timePairs);
return isOverlap(timePairs, isStrict);
}
复制代码
可以看出多个时间段的算法也适用于2个时间段,2个时间段只是其中的一个特例。
近期评论