我有一个 BookingDateRange 列表,其中 BookingDateRange 是:
public class BookingDateRange {
private Date fromDate;
private Date toDate;
//getters & setters of properties
}
要求:
- 我需要查找 BookingDate 列表中是否有任何日期重叠,比如 dateRangeList
- 如果是,找到所有重叠的日期范围对,比如 List of String say overlappingDatePairs
示例 1:
输入1:
dateRangeList[0] = 2012 年 12 月 23 日- 2012 年 12 月 27 日
dateRangeList[1] = 2012 年 12 月 14 日 - 2012 年 12 月 25 日
dateRangeList[2] = 2012 年 1 月 1 日 - 2012 年 1 月 23 日
输出1:
isOverlappingDates = true
重叠日期对 = [0_1]
示例 2:
输入2:
dateRangeList[0] = 2012 年 12 月 23 日- 2012 年 12 月 27 日
dateRangeList[1] = 2012 年 1 月 1 日 - 2012 年 1 月 23 日
输出2:
isOverlappingDates = 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 遇到了一些解决方案。但都不能完全满足要求。
谢谢, 什卡
最佳答案
这是 O(nlog(n)),或者显然如果有很多碰撞,它是 O(碰撞次数)。我曾经工作过的一家公司用类似的东西作为面试问题。
private static class BookingTuple implements Comparable<BookingTuple> {
public final Date date;
public final boolean isStart;
public final int id;
public BookingTuple(Date date, boolean isStart, int id) {
this.date = date;
this.isStart = isStart;
this.id = id;
}
@Override
public int compareTo(BookingTuple other) {
int dateCompare = date.compareTo(other.date);
if (dateCompare != 0) {
return dateCompare;
} else {
if (!isStart && other.isStart) {
return -1;
} else if (isStart && !other.isStart) {
return 1;
} else {
return 0;
}
}
}
}
public static boolean isOverlappingDates(List<BookingDateRange> dateRangeList, List<String> overlappingDatePairs) {
List<BookingTuple> list = new ArrayList<BookingTuple>();
for (int i = 0; i < dateRangeList.size(); i++) {
Date from = dateRangeList.get(i).getFromDate();
Date to = dateRangeList.get(i).getToDate();
list.add(new BookingTuple(from, true, i));
list.add(new BookingTuple(to, false, i));
}
Collections.sort(list);
boolean overlap = false;
HashSet<Integer> active = new HashSet<Integer>();
for (BookingTuple tuple : list) {
if (!tuple.isStart) {
active.remove(tuple.id);
} else {
for (Integer n : active) {
overlappingDatePairs.add(n + "_" + tuple.id);
overlap = true;
}
active.add(tuple.id);
}
}
return overlap;
}
关于java - 从给定的日期范围列表中查找所有重叠的日期范围,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12573512/