Giả sử chúng ta có một mảng các cặp P. Trong đó P [i] có dạng (l, r) và có một số khác k. Hãy xem xét chúng ta sẽ đọc một cuốn sách có n chương. sao cho một trang của cuốn sách thuộc về chính xác một chương và mỗi chương chứa ít nhất một trang. Chúng tôi đã đọc một số trang và đánh dấu trang có số k là trang đầu tiên chưa được đọc. Chúng ta phải tìm số chương mà chúng ta chưa đọc hết. P [i] đại diện cho sắp xếp số trang của chương.
Vì vậy, nếu đầu vào giống như P =[[1, 3], [4, 7], [8, 11]]; k =4, thì đầu ra sẽ là 2, vì chúng ta đã đọc chương đầu tiên, hai chương khác vẫn còn để đọc.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
n := size of P for initialize i := 1, when i <= n, update (increase i by 1), do: if k >= P[i - 1, 0] and k <= P[i - 1, 1], then: return n - i + 1 return 0
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> P, int k){
int n = P.size();
for (int i = 1; i <= n; i++){
if (k >= P[i - 1][0] && k <= P[i - 1][1])
return n - i + 1;
}
return 0;
}
int main(){
vector<vector<int>> P = { { 1, 3 }, { 4, 7 }, { 8, 11 } };
int k = 4;
cout << solve(P, k) << endl;
} Đầu vào
{ { 1, 3 }, { 4, 7 }, { 8, 11 } }, 4 Đầu ra
2