Pertanyaan Tentukan Apakah Dua Tanggal Berkisar Tumpang Tindih


Dengan dua rentang tanggal, apa cara paling sederhana atau paling efisien untuk menentukan apakah dua rentang tanggal tumpang tindih?

Sebagai contoh, misalkan kita memiliki rentang yang dilambangkan dengan variabel DateTime StartDate1 untuk EndDate1  dan  StartDate2 untuk EndDate2.


984
2017-11-28 14:48


asal


Jawaban:


(StartA <= EndB) dan (EndA> = StartB)

Bukti:
Biarkan Kondisi A Berarti bahwa DateRange A Sepenuhnya Setelah DateRange B
_ |---- DateRange A ------| |---Date Range B -----| _
  (Benar jika StartA > EndB)

Biarkan KondisiB Berarti bahwa DateRange A Sepenuhnya Sebelum DateRange B
|---- DateRange A -----| _ _ |---Date Range B ----|
 (Benar jika EndA < StartB)

Kemudian Tumpang Tindih ada jika B & B A tidak benar -
 (Jika satu rentang tidak sepenuhnya setelah yang lain,
   atau sepenuhnya sebelum yang lain,      maka mereka harus tumpang tindih.)

Sekarang salah satunya Hukum De Morgan mengatakan itu:

Not (A Or B)  <=> Not A And Not B

Yang diterjemahkan menjadi: (StartA <= EndB) and (EndA >= StartB)


CATATAN: Ini termasuk kondisi di mana tepinya saling tumpang tindih. Jika Anda ingin mengecualikan itu,
mengubah >= operator ke >, dan <=  untuk < 


CATATAN 2. Terima kasih kepada @Baodad, lihat blog ini, tumpang tindih yang sebenarnya setidaknya dari:
  { endA-startA, endA - startB, endB-startA, endB - startB }

(StartA <= EndB) and (EndA >= StartB) (StartA <= EndB) and (StartB <= EndA)


CATATAN 3. Terima kasih kepada @tomosius, versi yang lebih pendek berbunyi:
DateRangesOverlap = max(start1, start2) < min(end1, end2)
Ini sebenarnya adalah pintasan sintaksis untuk apa yang merupakan implementasi yang lebih lama, yang termasuk pemeriksaan ekstra untuk memverifikasi bahwa tanggal mulai berada pada atau sebelum tanggal akhir. Turunkan ini dari atas:

Jika tanggal mulai dan akhir dapat rusak, mis., Jika mungkin startA > endA atau startB > endB, maka Anda juga harus memeriksa apakah semuanya sudah beres, jadi itu berarti Anda harus menambahkan dua aturan validitas tambahan:
(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB) atau:
(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB) atau,
(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB)) atau:
(Max(StartA, StartB) <= Min(EndA, EndB) 

Tetapi untuk menerapkan Min() dan Max(), Anda harus kode, (menggunakan C terner untuk ketangkasan) ,:
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB) 


1869
2017-11-28 15:00



Saya percaya bahwa cukup untuk mengatakan bahwa keduanya berkisar tumpang tindih jika:

(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1)

320
2017-11-28 14:49



Artikel ini Perpustakaan Periode Waktu untuk .NET menggambarkan hubungan dua periode waktu oleh pencacahan PeriodRelation:

// ------------------------------------------------------------------------
public enum PeriodRelation
{
    After,
    StartTouching,
    StartInside,
    InsideStartTouching,
    EnclosingStartTouching,
    Enclosing,
    EnclosingEndTouching,
    ExactMatch,
    Inside,
    InsideEndTouching,
    EndInside,
    EndTouching,
    Before,
} // enum PeriodRelation

enter image description here


87
2018-04-08 22:42



Untuk alasan tentang hubungan temporal (atau hubungan interval lainnya, datanglah ke situ), pertimbangkan Aljabar Interval Allen. Ini menggambarkan 13 kemungkinan hubungan yang dapat dilakukan oleh dua interval terhadap satu sama lain. Anda dapat menemukan referensi lain - "Interval Allen" tampaknya merupakan istilah pencarian operasi. Anda juga dapat menemukan informasi tentang operasi ini di Snodgrass Mengembangkan Aplikasi Berorientasi Waktu di SQL (PDF tersedia online di URL), dan di Date, Darwen dan Lorentzos Data Temporal dan Model Relasional (2002) atau Waktu dan Teori Relasional: Database Temporal dalam Model Relasional dan SQL (2014; efektif edisi kedua TD & RM).


Jawaban singkat (ish) adalah: diberikan dua interval tanggal A dan B dengan komponen .start dan .end dan kendala .start <= .end, lalu dua interval tumpang tindih jika:

A.end >= B.start AND A.start <= B.end

Anda dapat mengatur penggunaan >= vs > dan <= vs < untuk memenuhi persyaratan Anda untuk tingkat tumpang tindih.


ErikE berkomentar:

Anda hanya bisa mendapatkan 13 jika Anda menghitung hal-hal lucu ... Saya bisa mendapatkan "15 kemungkinan hubungan yang dua interval dapat memiliki" ketika saya gila dengan itu. Dengan perhitungan yang masuk akal, saya hanya mendapatkan enam, dan jika Anda membuang peduli apakah A atau B datang lebih dulu, saya hanya mendapatkan tiga (tidak ada persimpangan, sebagian berpotongan, satu sepenuhnya dalam lainnya). 15 berjalan seperti ini: [sebelum: sebelum, mulai, dalam, akhir, setelah], [mulai: mulai, dalam, akhir, setelah], [dalam: dalam, akhir, setelah], [akhir: akhir, setelah], [ setelah: sesudahnya].

Saya pikir Anda tidak dapat menghitung dua entri 'sebelum: sebelum' dan 'sesudah: sesudah'. Saya bisa melihat 7 entri jika Anda menyamakan beberapa relasi dengan invers mereka (lihat diagram di URL Wikipedia yang direferensikan; ini memiliki 7 entri, 6 di antaranya memiliki invers yang berbeda, dengan sama tidak memiliki invers yang berbeda). Dan apakah tiga masuk akal tergantung pada kebutuhan Anda.

----------------------|-------A-------|----------------------
    |----B1----|
           |----B2----|
               |----B3----|
               |----------B4----------|
               |----------------B5----------------|
                      |----B6----|
----------------------|-------A-------|----------------------
                      |------B7-------|
                      |----------B8-----------|
                         |----B9----|
                         |----B10-----|
                         |--------B11--------|
                                      |----B12----|
                                         |----B13----|
----------------------|-------A-------|----------------------

66
2017-11-30 06:54



Jika tumpang tindih itu sendiri harus dihitung juga, Anda dapat menggunakan rumus berikut:

overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))
if (overlap > 0) { 
    ...
}

25
2017-09-06 02:07



Semua solusi yang memeriksa banyak kondisi berdasarkan di mana kisaran dalam kaitannya dengan satu sama lain dapat sangat disederhanakan oleh hanya memastikan bahwa rentang tertentu dimulai lebih awal! Anda memastikan bahwa rentang pertama dimulai lebih awal (atau pada saat yang sama) dengan menukar rentang jika perlu di awal.

Kemudian, Anda dapat mendeteksi tumpang tindih jika rentang lainnya mulai kurang dari atau sama dengan ujung rentang pertama (jika rentang inklusif, berisi waktu mulai dan akhir) atau kurang dari (jika rentang sudah termasuk awal dan akhir eksklusif) .

Dengan asumsi inklusif di kedua ujungnya, hanya ada empat kemungkinan yang tidak tumpang tindih:

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 overlap
                        |--->   range 2 no overlap

Titik akhir rentang 2 tidak masuk ke dalamnya. Jadi, dalam pseudo-code:

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    if r2.s > r1.e:
        return false
    return true

Ini bisa disederhanakan menjadi lebih dalam:

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    return r2.s <= r1.e

Jika rentang inklusif di awal dan eksklusif di bagian akhir, Anda hanya perlu mengganti > dengan >= di yang kedua if pernyataan (untuk segmen kode pertama: di segmen kode kedua, Anda akan menggunakan < daripada <=):

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 no overlap
                        |--->   range 2 no overlap

Anda sangat membatasi jumlah pemeriksaan yang harus Anda lakukan karena Anda menghapus separuh dari ruang masalah awal dengan memastikan rentang 1 tidak pernah dimulai setelah rentang 2.


16
2017-08-06 02:39



Berikut ini adalah solusi lain menggunakan JavaScript. Spesialisasi solusi saya:

  • Menangani nilai nol sebagai tak terhingga
  • Asumsikan bahwa batas bawah bersifat inklusif dan batas atas eksklusif.
  • Dilengkapi dengan banyak tes

Tes didasarkan pada bilangan bulat, tetapi karena objek tanggal dalam JavaScript sebanding, Anda hanya dapat memasukkan dua objek tanggal juga. Atau Anda bisa melempar cap waktu milidetik.

Kode:

/**
 * Compares to comparable objects to find out whether they overlap.
 * It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
 * A null value is interpreted as infinity
 */
function intervalsOverlap(from1, to1, from2, to2) {
    return (to2 === null || from1 < to2) && (to1 === null || to1 > from2);
}

Tes:

describe('', function() {
    function generateTest(firstRange, secondRange, expected) {
        it(JSON.stringify(firstRange) + ' and ' + JSON.stringify(secondRange), function() {
            expect(intervalsOverlap(firstRange[0], firstRange[1], secondRange[0], secondRange[1])).toBe(expected);
        });
    }

    describe('no overlap (touching ends)', function() {
        generateTest([10,20], [20,30], false);
        generateTest([20,30], [10,20], false);

        generateTest([10,20], [20,null], false);
        generateTest([20,null], [10,20], false);

        generateTest([null,20], [20,30], false);
        generateTest([20,30], [null,20], false);
    });

    describe('do overlap (one end overlaps)', function() {
        generateTest([10,20], [19,30], true);
        generateTest([19,30], [10,20], true);

        generateTest([10,20], [null,30], true);
        generateTest([10,20], [19,null], true);
        generateTest([null,30], [10,20], true);
        generateTest([19,null], [10,20], true);
    });

    describe('do overlap (one range included in other range)', function() {
        generateTest([10,40], [20,30], true);
        generateTest([20,30], [10,40], true);

        generateTest([10,40], [null,null], true);
        generateTest([null,null], [10,40], true);
    });

    describe('do overlap (both ranges equal)', function() {
        generateTest([10,20], [10,20], true);

        generateTest([null,20], [null,20], true);
        generateTest([10,null], [10,null], true);
        generateTest([null,null], [null,null], true);
    });
});

Hasil saat dijalankan dengan karma & melati & PhantomJS:

PhantomJS 1.9.8 (Linux): Dilaksanakan 20 dari 20 SUCCESS (0,003 detik / 0,004 detik)


12
2018-03-13 13:19



Saya tahu ini telah ditandai sebagai bahasa-agnostik, tetapi untuk Anda semua yang menerapkan di Java: Jangan menemukan kembali roda dan menggunakan Joda Time.

http://joda-time.sourceforge.net/api-release/org/joda/time/base/AbstractInterval.html#overlaps(org.joda.time.ReadableInterval)


8
2017-10-13 15:10



Saya akan melakukannya

StartDate1.IsBetween(StartDate2, EndDate2) || EndDate1.IsBetween(StartDate2, EndDate2)

Dimana IsBetween adalah sesuatu seperti

    public static bool IsBetween(this DateTime value, DateTime left, DateTime right) {
        return (value > left && value < right) || (value < left && value > right);
    }

7
2017-11-28 14:51



Solusi yang dipasang di sini tidak berfungsi untuk semua rentang yang tumpang tindih ...

---------------------- | ------- A ------- | ----------- -----------
    | ---- B1 ---- |
           | ---- B2 ---- |
               | ---- B3 ---- |
               | ---------- B4 ---------- |
               | ---------------- B5 ---------------- |
                      | ---- B6 ---- |
---------------------- | ------- A ------- | ----------- -----------
                      | ------ B7 ------- |
                      | ---------- B8 ----------- |
                         | ---- B9 ---- |
                         | ---- B10 ----- |
                         | -------- B11 -------- |
                                      | ---- B12 ---- |
                                         | ---- B13 ---- |
---------------------- | ------- A ------- | ----------- -----------

solusi saya bekerja adalah:

DAN (
  ('start_date' ANTARA STARTDATE DAN AKHIRNYA) - melayani untuk akhir tanggal dalam dan akhir
  ATAU
  ('end_date' ANTARA STARTDATE DAN AKHIRNYA) - melayani untuk tanggal dalam dan mulai tanggal di luar
  ATAU
  (STARTDATE ANTARA 'start_date' DAN 'end_date') - hanya satu yang diperlukan untuk jangkauan luar di mana tanggal berada di dalam.
)

5
2017-11-05 08:24