Apa cara paling efisien untuk menguji dua rentang bilangan bulat untuk tumpang tindih?

Diberikan dua rentang bilangan bulat inklusif [x1: x2] dan [y1: y2], di mana x1 ≤ x2 dan y1 ≤ y2, apa cara paling efisien untuk menguji apakah ada tumpang tindih dari kedua rentang?

Implementasi sederhana adalah sebagai berikut:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

Tapi saya berharap ada cara yang lebih efisien untuk menghitung ini.

Metode apa yang paling efisien dalam hal operasi paling sedikit.

Apa artinya rentang tumpang tindih? Itu berarti ada beberapa angka C yang ada di kedua rentang, yaitu

x1 <= C <= x2

dan

y1 <= C <= y2

Sekarang, jika kita diizinkan untuk mengasumsikan bahwa rentangnya terbentuk dengan baik (sehingga x1 <= x2 dan y1 <= y2) maka cukup untuk menguji

x1 <= y2 && y1 <= x2

Diberi dua rentang [x1, x2], [y1, y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

Ini dapat dengan mudah melengkungkan otak manusia normal, jadi saya telah menemukan pendekatan visual agar lebih mudah dipahami:

le Penjelasan

Jika dua rentang "terlalu gemuk" untuk masuk dalam slot yang persis jumlah dari lebar keduanya, maka keduanya tumpang tindih.

Untuk rentang [a1, a2]dan [b1, b2]ini akan menjadi:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}

Jawaban bagus dari Simon , tetapi bagi saya lebih mudah untuk memikirkan kasus terbalik.

Kapan 2 rentang tidak tumpang tindih? Mereka tidak tumpang tindih ketika salah satu dari mereka mulai setelah yang lain berakhir:

dont_overlap = x2 < y1 || x1 > y2

Sekarang mudah untuk mengekspresikan ketika mereka tumpang tindih:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

Mengurangi Minimum dari ujung rentang dari Maksimum awal tampaknya melakukan trik. Jika hasilnya kurang dari atau sama dengan nol, kami memiliki tumpang tindih. Ini memvisualisasikannya dengan baik:

Saya kira pertanyaannya adalah tentang kode tercepat, bukan kode terpendek. Versi tercepat harus menghindari cabang, sehingga kita dapat menulis sesuatu seperti ini:

untuk kasus sederhana:

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

atau, untuk kasus ini:

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};

return x2 >= y1 && x1 <= y2;

Jika Anda berurusan dengan, diberikan dua rentang [x1:x2]dan [y1:y2], kisaran urutan alami / anti-alami pada saat yang sama di mana:

• tatanan alami: x1 <= x2 && y1 <= y2atau
• tatanan anti-alami: x1 >= x2 && y1 >= y2

maka Anda mungkin ingin menggunakan ini untuk memeriksa:

mereka tumpang tindih <=> (y2 - x1) * (x2 - y1) >= 0

di mana hanya empat operasi yang terlibat:

• dua pengurangan
• satu perkalian
• satu perbandingan

Jika seseorang mencari satu-liner yang menghitung tumpang tindih aktual:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

Jika Anda ingin pasangan lebih sedikit operasi, tetapi pasangan lebih banyak variabel:

bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations

Pikirkan dengan cara terbalik : bagaimana membuat 2 rentang tidak tumpang tindih ? Diberikan [x1, x2], maka [y1, y2]harus di luar [x1, x2] , yaitu y1 < y2 < x1 or x2 < y1 < y2yang setara dengan y2 < x1 or x2 < y1.

Oleh karena itu, kondisi untuk membuat 2 rentang tumpang tindih:, not(y2 < x1 or x2 < y1)yang setara dengan y2 >= x1 and x2 >= y1(sama dengan jawaban yang diterima oleh Simon).

Anda sudah memiliki representasi paling efisien - ini adalah minimum yang perlu diperiksa kecuali Anda tahu pasti bahwa x1 <x2 dll, kemudian gunakan solusi yang telah disediakan orang lain.

Anda mungkin harus memperhatikan bahwa beberapa kompiler benar-benar akan mengoptimalkan ini untuk Anda - dengan mengembalikan segera setelah salah satu dari keempat ekspresi tersebut mengembalikan true. Jika satu mengembalikan true, maka hasil akhirnya - jadi yang lain hanya bisa dilewati.

Kasus saya berbeda. saya ingin memeriksa dua rentang waktu yang tumpang tindih. seharusnya tidak ada tumpang tindih satuan waktu. di sini adalah implementasi Go.

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

Uji kasus

if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 6, 9) != true {
        t.Error("Expected 2,8,6,9 to equal TRUE")
    }

    if CheckRange(2, 8, 8, 9) != false {
        t.Error("Expected 2,8,8,9 to equal FALSE")
    }

    if CheckRange(2, 8, 4, 6) != true {
        t.Error("Expected 2,8,4,6 to equal TRUE")
    }

    if CheckRange(2, 8, 1, 9) != true {
        t.Error("Expected 2,8,1,9 to equal TRUE")
    }

    if CheckRange(4, 8, 1, 3) != false {
        t.Error("Expected 4,8,1,3 to equal FALSE")
    }

    if CheckRange(4, 8, 1, 4) != false {
        t.Error("Expected 4,8,1,4 to equal FALSE")
    }

    if CheckRange(2, 5, 6, 9) != false {
        t.Error("Expected 2,5,6,9 to equal FALSE")
    }

    if CheckRange(2, 5, 5, 9) != false {
        t.Error("Expected 2,5,5,9 to equal FALSE")
    }

Anda dapat melihat ada pola XOR dalam perbandingan batas

Ini versi saya:

int xmin = min(x1,x2)
  , xmax = max(x1,x2)
  , ymin = min(y1,y2)
  , ymax = max(y1,y2);

for (int i = xmin; i < xmax; ++i)
    if (ymin <= i && i <= ymax)
        return true;

return false;

Kecuali jika Anda menjalankan beberapa pemeriksa rentang berkinerja tinggi pada milyaran bilangan bulat yang luas, versi kami akan melakukan hal yang sama. Maksud saya adalah, ini adalah optimasi mikro.