要查找所有日期從給定的列表中重疊的日期範圍的範圍

Question

我有BookingDateRange的一個List，BookingDateRange是：

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

     //getters & setters of properties 
    } 

要求：

1. 我需要找到如果有的話日期重疊在BookingDate列表中說dateRangeList
2. 如果是，找到所有重疊的日期範圍對say字符串列表說overlapDatePairs

例1：

輸入1：

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

dateRangeList [1] =二〇一二年十二月一十四日 - 2012年12月25日

dateRangeList [2] = 1 jan 2012 - 23 jan 2012

輸出1：

個

isOverlappingDates =真

overlappingDatePairs = [0_1]

例2：

輸入2：

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

dateRangeList [1] = 1月2012年 - 23月2012

輸出2：

isOverlappingDates =假

overlappingDatePairs = []

我的解決方案：

/** 
* 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上遇到過幾個解決方案。但是他們都不能完全滿足這個要求。

感謝， Shikha

Answer 1

這裏是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; 
} 

Answer 2

我不認爲你可以做的更好，因爲你必須每BookingDateRange與別人比較......

因此，需要O(n) comparisons per element和你有n elements

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

Answer 3

我的解決方案將交易的複雜性存儲器。它假設日期的範圍相對有限（您不混合5000BC和6000AD的日期）。

1創建一個Map<String, List<Range>>。

2對於每個範圍，選擇第一個日期並將其轉換爲GregorianCalendar。以「yyyy/MM/dd」格式（或類似格式）獲取日期。

2a如果「yyyy/MM/dd」字符串已經在Map中，請將新Range添加到列表中。

2b如果不是，則添加包含範圍的新列表的條目。

2c每天增加GregorianCalendar。重複，直到達到範圍中的最後一個日期。

3重複所有的範圍。

4列出地圖的關鍵字（如果您使用「yyyy/MM/dd」格式排序很簡單）。檢查關聯列表的大小。