Cari indeks selang tak bertindih yang paling hampir di sebelah kanan setiap selang N yang diberikan

Perwakilan selang standard biasanya termasuk set titik permulaan dan penamat yang berpasangan. Mencari selang tidak bertindih terdekat di sebelah kanan setiap selang yang ditentukan membentuk dilema semasa kami. Tugas ini sangat penting dalam banyak aplikasi yang berbeza, seperti peruntukan sumber dan penjadualan, kerana ia melibatkan mengenal pasti selang seterusnya yang tidak bersilang atau mengandungi selang semasa.

Tatabahasa

Untuk membantu memahami demonstrasi kod yang akan kami tunjukkan, mari kita lihat sintaks yang akan kami gunakan dahulu sebelum menyelami algoritma.

// Define the Interval structure
struct Interval {
   int start;
   int end;
};

// Function to find the index of closest non-overlapping interval
vector<int> findClosestNonOverlappingInterval(const vector<interval>& intervals) {
   // Implementation goes here
}
</interval></int>

Algoritma

Menyelesaikan masalah ini memerlukan pendekatan tersusun yang berpusat pada selang lelaran dalam susunan terbalik sambil mengekalkan timbunan indeks yang menunjuk kepada rakan kongsi tidak bertindih terdekat mereka. Berikut ialah langkah ringkas tetapi berkesan tentang cara algoritma yang dicadangkan kami menyelesaikan masalah ini -

• Buat tindanan kosong untuk menyimpan indeks julat tidak bertindih.

• Mulakan vektor indeks dengan saiz yang sama dengan bilangan selang, berlapik dengan -1 untuk menunjukkan bahawa selang tidak bertindih tidak ditemui.

• Lintas selang dari kanan ke kiri.

• Jika tindanan tidak kosong dan terdapat kawasan keratan rentas antara selang semasa dan selang atas, teruskan untuk menghapuskan (pop) indeks paling atas itu daripada tindanan tersebut.

• Untuk memastikan perwakilan yang tepat, jika tindanan kosong, kedudukan indeks ditetapkan -1 dalam vektor yang mewakili selang semasa. Ini bermakna tiada selang tidak bertindih di sebelah kanan.

• Adalah amat disyorkan untuk memastikan timbunan yang kami tentukan mempunyai elemen sebelum mencuba tugasan ini jika tidak ralat akan berlaku. Selepas mengesahkan bahawa kami mempunyai satu atau lebih elemen pada struktur tersebut, kami boleh melakukan ini dengan meminta vektor selang semasa menetapkan nilai indeksnya sama dengan elemen yang sepadan di kedudukan teratas pada struktur yang kami kenal pasti dan maklumat indeksnya yang sepadan. . Masukkan ke dalam struktur yang sama untuk melakukan operasi.

• Ulang langkah 3-7 sehingga semua selang telah diproses.

• Mengembalikan vektor indeks.

Kaedah

Untuk menyelesaikan dilema ini, kita akan melihat dua strategi berbeza.

Kaedah 1: Brute force cracking

Satu strategi yang mungkin untuk menyelesaikan masalah ini ialah menggunakan kekerasan. Pada asasnya, ini memerlukan pemeriksaan setiap selang individu dan kemudian membandingkannya dengan semua selang di sebelah kanannya sehingga tiada pilihan persimpangan menjadi jelas. Namun begitu. Perlu diingat bahawa menggunakan kaedah ini menghasilkan kerumitan masa O(N^2). Di mana N mewakili jumlah bilangan selang yang mengambil bahagian dalam proses pemeriksaan.

Tatabahasa

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   for (int i = 0; i < intervals.size(); i++) {
      for (int j = i + 1; j < intervals.size(); j++) {
         if (intervals[i].end < intervals[j].start) {
            result[i] = j;
            break;
         }
      }
   }
   return result;
}

Contoh

Contoh

#include 
#include 

using namespace std;

// Define the Interval structure
struct Interval {
   int start;
   int end;
};

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   for (int i = 0; i < intervals.size(); i++) {
      for (int j = i + 1; j < intervals.size(); j++) {
         if (intervals[i].end < intervals[j].start) {
            result[i] = j;
            break;
         }
      }
   }
   return result;
}

int main() {
   // Define intervals
   vector intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};

   // Find the index of closest non-overlapping interval for each interval
   vector closestIndices = findClosestNonOverlappingInterval(intervals);

   // Print the results
   for (int i = 0; i < intervals.size(); i++) {
      cout << "Interval [" << intervals[i].start << ", " << intervals[i].end << "] ";
      if (closestIndices[i] != -1) {
         cout << "has closest non-overlapping interval at index " << closestIndices[i] << endl;
      } else {
         cout << "has no non-overlapping interval to the right" << endl;
      }
   }
   return 0;
}

Output

Interval [1, 3] has closest non-overlapping interval at index 2
Interval [2, 4] has closest non-overlapping interval at index 2
Interval [5, 7] has closest non-overlapping interval at index 4
Interval [6, 9] has no non-overlapping interval to the right
Interval [8, 10] has no non-overlapping interval to the right

Kaedah 2: Penyelesaian optimum

Satu pendekatan yang sangat berjaya melibatkan penggunaan timbunan sebagai cara memantau selang tidak bertindih baru-baru ini. Kerumitan masa strategi ini ialah O(N) kerana tugas kita hanya memerlukan kita meneliti selang sekali.

Tatabahasa

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   stack<int> st;
   for (int i = intervals.size() - 1; i >= 0; i--) {
      while (!st.empty() && intervals[i].end >= intervals[st.top()].start) {
         st.pop();
      }
      if (!st.empty()) {
         result[i] = st.top();
      }
      st.push(i);
   }
   return result;
}

Contoh

Contoh

#include 
#include 

using namespace std;

// Define the Interval structure
struct Interval {
   int start;
   int end;
};

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   for (int i = 0; i < intervals.size(); i++) {
      for (int j = i + 1; j < intervals.size(); j++) {
         if (intervals[i].end < intervals[j].start) {
            result[i] = j;
            break;
         }
      }
   }
   return result;
}

int main() {
   // Define intervals
   vector intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};
   
   // Find the index of closest non-overlapping interval for each interval
   vector closestIndices = findClosestNonOverlappingInterval(intervals);
   
   // Print the results
   for (int i = 0; i < intervals.size(); i++) {
      cout << "Interval [" << intervals[i].start << ", " << intervals[i].end << "] ";
      if (closestIndices[i] != -1) {
         cout << "has closest non-overlapping interval at index " << closestIndices[i] << endl;
      } else {
         cout << "has no non-overlapping interval to the right" << endl;
      }
   }
   return 0;
}

Output

Interval [1, 3] has closest non-overlapping interval at index 2
Interval [2, 4] has closest non-overlapping interval at index 2
Interval [5, 7] has closest non-overlapping interval at index 4
Interval [6, 9] has no non-overlapping interval to the right
Interval [8, 10] has no non-overlapping interval to the right

Kesimpulan

Matlamat penerokaan kami adalah untuk mencari kedudukan terbaik indeks selang tidak bertindih yang paling hampir di sebelah kanan setiap selang yang diberikan dalam C++. Pertama, kita membincangkan kerumitan sintaksis secara mendalam, sambil mencadangkan algoritma dan mencadangkan dua penyelesaian yang berpotensi. Sebagai sebahagian daripada penyiasatan kami, kami menunjukkan cara pendekatan brute force dan pendekatan pengoptimuman berasaskan tindanan kami berfungsi dengan kod boleh laku yang berjaya diuji. Kaedah ini membolehkan anda dengan mudah mengenal pasti selang tidak bertindih yang paling hampir untuk mana-mana set tertentu.

Atas ialah kandungan terperinci Cari indeks selang tak bertindih yang paling hampir di sebelah kanan setiap selang N yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!