สมมติว่าเรามีอาร์เรย์ของคู่ P โดยที่ P[i] อยู่ในรูปแบบ (l, r) และมีตัวเลขอื่น k พิจารณาว่าเรากำลังอ่านหนังสือที่มี n บท เพื่อให้หนึ่งหน้าของหนังสืออยู่ในหนึ่งบทและแต่ละบทมีอย่างน้อยหนึ่งหน้า เราได้อ่านบางหน้าและทำเครื่องหมายหน้าที่มีหมายเลข k เป็นหน้าแรกที่ไม่ได้อ่าน เราต้องหาจำนวนบทที่เรายังอ่านไม่จบ P[i] หมายถึงช่วงหมายเลขหน้าบท
ดังนั้น หากอินพุตเป็นแบบ P =[[1, 3], [4, 7], [8, 11]]; k =4 แล้วผลลัพธ์จะเป็น 2 เนื่องจากเราอ่านบทแรกไปแล้ว จึงมีอีกสองบทให้อ่าน
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
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
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
{ { 1, 3 }, { 4, 7 }, { 8, 11 } }, 4 ผลลัพธ์
2
