8

BookingDateRangeのリストがあります。BookingDateRangeは次のとおりです。

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

        //getters & setters of properties
   }

要件：

  1. BookingDateのリストでdateRangeListと言う日付が重複していないかどうかを確認する必要があります
  2. はいの場合、重複するすべての日付範囲のペアを検索します。たとえば、文字列のリストは、overlapingDatePairsと言います。

例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を他の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そうでない場合は、範囲を含む新しいリストを使用してエントリを追加します。

2c1日グレゴリオ暦を増やします。範囲内の最後の日付に達するまで繰り返します。

3すべての範囲で繰り返します。

4マップのキーを一覧表示します（「yyyy / MM / dd」形式を使用した場合、並べ替えは簡単です）。関連するリストのサイズを確認してください。

于 2012-09-24T22:06:07.430 に答える