นับจำนวนช่วงที่ค่าที่กำหนดอยู่ใน C++

กำหนดอาร์เรย์ 2 มิติ arr[][] ที่มีช่วงเวลาและค่า 'ค่า' ตัวเลข เป้าหมายคือการหาจำนวนช่วงเวลาที่มีอยู่ใน arr ระหว่างที่ค่าอยู่ ตัวอย่างเช่น ช่วงคือ [ [1,5], [3,7] ] และ value=4 จากนั้นจะอยู่ในช่วงเวลาทั้งสองนี้และนับเป็น 2

ตัวอย่าง

อินพุต

arr[4][2] = { { 1, 20 }, { 12, 25 }, { 32, 40 }, { 15, 18 } } value=16

ผลลัพธ์

Count of number of intervals in which a given value lies are: 3

คำอธิบาย

The value 16 lies between 1−20, 12−25 and 15−18

อินพุต

arr[4][2] = {{ 1, 20 }, { 20,30 }, { 30, 40 }, { 40, 50 }} value=60

ผลลัพธ์

Count of number of intervals in which a given value lies are: 0

คำอธิบาย

The value 60 is larger than all maximum ranges of intervals present in
arr[][].

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะสร้างอาร์เรย์ความถี่ arr_2[] สำหรับจำนวนทั้งหมดของช่วงที่อยู่ใน arr ดังนั้นสำหรับแต่ละช่วง arr[i][0] และ arr[i][1] ความถี่จะเพิ่มขึ้นใน arr_2[ arr[i][0 หรือ 1] ] ในตอนท้าย เราจะอัปเดตอาร์เรย์ความถี่ด้วย arr_2[i]=arr_2[i]+arr_2[i−1] เนื่องจากตัวเลขที่น้อยกว่า i-1 จะน้อยกว่า i ดังนั้นความถี่จะถูกเพิ่มเข้าไป ด้วยวิธีนี้เราจะได้ arr_2[value] ตามช่วงทั้งหมดที่ค่าอยู่

• รับอาร์เรย์จำนวนเต็ม arr[][] ที่มีช่วง

• รับค่าจำนวนเต็มเป็นอินพุต

• ฟังก์ชัน intervals_values(int arr[][2], int size, int value) รับค่า arr และค่า และส่งคืนค่าจำนวนช่วงที่ค่าที่กำหนดอยู่

• ใช้อาร์เรย์ความถี่ arr_2[].

• ลดระดับต่ำสุดและสูงสุดเป็น INT_MAX และ INT_MIN

• Traverse arr[][] ใช้ for loop จาก i=0 ถึง i

• ใช้ temp เป็นด้านซ้ายของช่วงและเพิ่มความถี่ใน arr_2[temp]

• ใช้ temp_2 เป็นช่วงที่ถูกต้องและเพิ่มความถี่ใน arr_2[temp_2+1]

• ถ้า tempสูงสุด ตั้งค่าสูงสุดเป็น temp_2.

• ข้ามอาร์เรย์ความถี่และอัปเดต arr_2[i]=arr_2[i]+arr_2[i+1].

• ในตอนท้ายส่งคืน arr_2[value] เป็นผลลัพธ์

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
#define max 1000
int intervals_values(int arr[][2], int size, int value){
   int arr_2[max];
   int low = INT_MAX;
   int highest = INT_MIN;
   for(int i = 0; i < size; i++){
      int temp = arr[i][0];
      arr_2[temp] = arr_2[temp] + 1;
      int temp_2 = arr[i][1];
      arr_2[temp_2 + 1] = arr_2[temp_2 + 1] − 1;
      if(temp < low){
         low = temp;
      }
      if(temp_2 > highest){
         highest = temp_2;
      }
   }
   for (int i = low; i <= highest; i++){
      arr_2[i] = arr_2[i] + arr_2[i − 1];
   }
   return arr_2[value];
}
int main(){
   int arr[4][2] = { { 3, 20 }, { 2, 13 }, { 25, 30 }, { 15, 40 } };
   int size = sizeof(arr) / sizeof(arr[0]);
   int value = 28;
   cout<<"Count the number of intervals in which a given value lies are:
   "<<intervals_values(arr, size, value);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count the number of intervals in which a given value lies are: 18830628