C++ में दिए गए मान वाले अंतरालों की संख्या गिनें

समस्या विवरण

एक 2D सरणी arr[][] दी गई है जिसमें अंतराल (intervals) हैं और एक संख्या value दी गई है। लक्ष्य उन अंतरालों की संख्या ज्ञात करना है जिनके बीच में value स्थित है। उदाहरण के लिए, अंतराल [[1,5], [3,7]] हैं और value=4 है, तो यह दोनों अंतरालों में स्थित है और गिनती 2 होगी।

उदाहरण

इनपुट

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

आउटपुट

दिए गए मान वाले अंतरालों की संख्या: 3

व्याख्या

मान 16, 1-20, 12-25 और 15-18 के बीच स्थित है

इनपुट

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

आउटपुट

दिए गए मान वाले अंतरालों की संख्या: 0

व्याख्या

मान 60, arr[][] में मौजूद सभी अंतरालों की अधिकतम सीमा से बड़ा है।

दृष्टिकोण

इस दृष्टिकोण में हम arr में मौजूद सभी रेंज की संख्याओं के लिए एक फ्रीक्वेंसी सरणी arr_2[] बनाते हैं। प्रत्येक रेंज के 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] मिलेगा जो उन सभी रेंज की संख्या होगी जिनमें value स्थित है।

एल्गोरिदम चरण

रेंज वाली पूर्णांक सरणी arr[][] लें।
एक पूर्णांक value इनपुट के रूप में लें।
फंक्शन intervals_values(int arr[][2], int size, int value) arr और value लेता है और दिए गए मान वाले अंतरालों की संख्या लौटाता है।
फ्रीक्वेंसी सरणी arr_2[] लें।
low और highest को क्रमशः INT_MAX और INT_MIN से प्रारंभ करें।
for लूप का उपयोग करके i=0 से i<size तक arr[][] को पार करें।
रेंज के बाएं मान को temp के रूप में लें और इसकी फ्रीक्वेंसी arr_2[temp] में बढ़ाएं।
रेंज के दाएं मान को temp_2 के रूप में लें और इसकी फ्रीक्वेंसी arr_2[temp_2 + 1] में घटाएं (डिफरेंस एरे तकनीक)।
यदि temp < low तो low = temp सेट करें और यदि temp_2 > highest तो highest = temp_2 सेट करें।
फ्रीक्वेंसी सरणी को पार करें और इसे अपडेट करें: arr_2[i] = arr_2[i] + arr_2[i-1]।
अंत में arr_2[value] को परिणाम के रूप में लौटाएं।

C++ कोड उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000

int intervals_values(int arr[][2], int size, int value) {
    int arr_2[MAX] = {0};
    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 << "दिए गए मान वाले अंतरालों की संख्या: " << intervals_values(arr, size, value);
    return 0;
}

आउटपुट

दिए गए मान वाले अंतरालों की संख्या: 2