8

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

    public class BookingDateRange {
        private Date fromDate;
        private Date toDate;

        //getters & setters of properties
   }

要求：

  1. 我需要查找 BookingDate 列表中是否有任何日期重叠，例如 dateRangeList
  2. 如果是，请找到所有重叠的日期范围对，比如字符串列表，比如重叠日期对

示例 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 遇到了一些解决方案。但没有一个能完全满足要求。

谢谢， 希哈

4

3 回答 3

6

这是 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;
}
于 2012-09-24T22:41:00.887 回答
2

我认为你不能做得更好，因为你必须将每个 BookingDateRange 与其他人进行比较......

所以它需要O(n) comparisons per element ，你有n elements

所以 n * n = O(n^2)

于 2012-09-24T22:03:58.050 回答
0

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

1 创建一个Map<String, List<Range>>.

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

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

2b 如果不是，则使用包含范围的新列表添加条目。

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

3 对所有范围重复此操作。

4 列出 Map 的键（如果您使用“yyyy/MM/dd”格式排序是微不足道的）。检查关联列表的大小。

于 2012-09-24T22:06:07.430 回答