我有一个 BookingDateRange 列表,其中 BookingDateRange 是:
public class BookingDateRange {
private Date fromDate;
private Date toDate;
//getters & setters of properties
}
要求:
- 我需要查找 BookingDate 列表中是否有任何日期重叠(例如 dateRangeList)
- 如果是,找到所有重叠的日期范围对,例如字符串列表,例如重叠日期对
Example1:
Input1:
dateRangeList[0] = 2012年12月23日- 2012年12月27日
dateRangeList[1] = 2012 年 12 月 14 日 - 2012 年 12 月 25 日
日期范围列表[2] = 2012 年 1 月 1 日 - 2012 年 1 月 23 日
Output1:
重叠日期 = true
重叠日期对 = [0_1]
示例2:
Input2:
dateRangeList[0] = 2012年12月23日- 2012年12月27日
日期范围列表[1] = 2012 年 1 月 1 日 - 2012 年 1 月 23 日
Output2:
重叠日期 = false
重叠日期对 = []
我的解决方案:
/**
* Checks if any of the dates overlap.
*
* @param dateRangeList the date range list
* @param overlappingDatePairs the overlapping date pairs where overlappingDatePair is stored in the format dateRange1_dateRange2
* @return true, if any of the dates overlap.
*/
public static boolean isOverlappingDates(
List<BookingDateRange> dateRangeList,
List<String> overlappingDatePairs) {
boolean isOverlap = false;
for (int index1 = 0; index1 < dateRangeList.size(); index1++) {
for (int index2 = index1 + 1; index2 < dateRangeList.size(); index2++) {
// Overlap exists if (StartA <= EndB) and (EndA >= StartB)
Date startA = dateRangeList.get(index1).getFromDate();
Date endA = dateRangeList.get(index1).getToDate();
Date startB = dateRangeList.get(index2).getFromDate();
Date endB = dateRangeList.get(index2).getToDate();
boolean isStartABeforeEndB = (startA.compareTo(endB)) < 0;
boolean isEndAAfterStartB = (endA.compareTo(startB)) > 0;
boolean isCurrentPairOverlap = false;
isCurrentPairOverlap = isStartABeforeEndB && isEndAAfterStartB;
if (isCurrentPairOverlap) {
overlappingDatePairs.add(index1 + "_" + index2);
isOverlap = true;
}
}
}
return isOverlap;
}
这种方法的复杂度是O(n^2)。是否可能有更好的复杂性?无法得出具有更好复杂性的算法。
SO 确实遇到了一些解决方案。但它们都不能完全满足要求。
谢谢,
什卡