从给定的日期范围列表中查找所有重叠的日期范围

我有一个BookingDateRange列表，其中BookingDateRange是：

public class BookingDateRange { private Date fromDate; private Date toDate; //getters & setters of properties } 

需求：

1. 我需要查找在BookingDate列表中是否有任何日期重叠，如dateRangeList
2. 如果是，找到重叠的所有日期范围对，比如说List of String说overlapDatePairs

例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

overlapDatePairs = [0_1]

例2：

输入2：

dateRangeList [0] = 2012年12月23日至2012年12月27日

dateRangeList [1] = 2012年1月1日 – 2012年1月23日

输出2：

isOverlappingDates = false

overlapDatePairs = []

我的解决方案

 /** * 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 dateRangeList, List 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 = 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 isCurrentPairOverlap = false; isCurrentPairOverlap = isStartABeforeEndB && isEndAAfterStartB; if (isCurrentPairOverlap) { overlappingDatePairs.add(index1 + "_" + index2); isOverlap = true; } } } return isOverlap; } 

这种方法的复杂性是O（n ^ 2）。 更复杂的可能吗？ 无法获得具有更好复杂性的算法。

在SO上遇到了一些解决方案。 但它们都不能完全满足要求。

谢谢，Shikha

Answer 1

这是O（nlog（n）），或者显然如果有很多碰撞，那就是O（碰撞次数）。 我曾经工作过的公司使用类似于此的面试问题。

 private static class BookingTuple implements Comparable { 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 dateRangeList, List overlappingDatePairs) { List list = new ArrayList(); 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 active = new HashSet(); 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; } 

Answer 2

我不认为你可以做得更好，因为你必须将每个BookingDateRange与其他人比较……

因此， O(n) comparisons per element需要进行O(n) comparisons per element并且您有n elements

因此n * n = O(n^2)

Answer 3

我的解决方案将交换内存的复杂性。 它假设日期范围相对有限（您没有混合日期从5000BC和6000AD）。

1创建Map> 。

2对于每个范围，选择第一个日期并将其转换为GregorianCalendar 。 获取格式为“yyyy / MM / dd”（或类似）的日期。

2a如果“yyyy / MM / dd”字符串已在Map中，请将新范围添加到列表中。

2b如果不是，请添加包含范围的新List的条目。

2c每天增加GregorianCalendar。 重复直到达到范围中的最后一个日期。

3对所有范围重复上述操作。

4列出Map的键（如果使用“yyyy / MM / dd”格式，则排序很简单）。 检查相关列表的大小。