Cho n đoạn [L[i], R[i]]. Tìm chỉ số (0-based) của đoạn bao phủ tất cả n-1 đoạn còn lại. Nếu không có, trả về -1. Ví dụ: L=[2,4,3,1], R=[4,6,7,9] → chỉ số 3 (đoạn [1,9] bao phủ tất cả).
Vì tất cả L, R đều distinct, tìm đoạn có L nhỏ nhất và R lớn nhất. Nếu cùng một đoạn thì đó là đáp án, ngược lại không tồn tại.
Ví dụ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findCoveringSegment(vector<int> L, vector<int> R) {
int n = L.size();
int minL = *min_element(L.begin(), L.end());
int maxR = *max_element(R.begin(), R.end());
for (int i = 0; i < n; i++) {
if (L[i] == minL && R[i] == maxR)
return i;
}
return -1;
}
int main() {
vector<int> L = {2, 4, 3, 1};
vector<int> R = {4, 6, 7, 9};
cout << "Index of covering segment: " << findCoveringSegment(L, R);
}
Kết quả
Index of covering segment: 3