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

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

ตัวอย่าง

Input

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

Output

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

Explanation

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

Input

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

Output

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

Explanation

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 or 1]] ในที่สุดจะอัปเดตอาร์เรย์ความถี่ด้วย arr_2[i] = arr_2[i] + arr_2[i-1] เนื่องจากตัวเลขที่น้อยกว่า i-1 จะน้อยกว่า i ด้วย ดังนั้นความถี่จะถูกรวมกัน ด้วยวิธีนี้จะได้ arr_2[value] เป็นจำนวนช่วงทั้งหมดที่ value อยู่ในนั้น

• รับอาร์เรย์จำนวนเต็ม arr[][] ที่เก็บช่วงต่างๆ
• รับค่า value เป็นจำนวนเต็ม
• ฟังก์ชัน intervals_values(int arr[][2], int size, int value) รับ arr และ value แล้วคืนค่าจำนวนช่วงที่ value อยู่ในนั้น
• สร้างอาร์เรย์ความถี่ arr_2[]
• กำหนด low และ highest เป็น INT_MAX และ INT_MIN ตามลำดับ
• วนลูปผ่าน arr[][] จาก i=0 ถึง i<size
• เก็บค่าด้านซ้ายของช่วงใน temp และเพิ่มความถี่ใน arr_2[temp]
• เก็บค่าด้านขวาของช่วงใน temp_2 และลดความถี่ใน arr_2[temp_2 + 1]
• อัปเดต low และ highest ตามค่าที่ได้
• วนลูปอัปเดตอาร์เรย์ความถี่: 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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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