Find least non | C ++ program to find the least non - overlapping number from a given set intervals ; function to find the smallest non - overlapping number ; create a visited array ; find the first missing value ; Driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1e5 + 5 ; void find_missing ( vector < pair < int , int > > interval ) { vector < int > vis ( MAX ) ; for ( int i = 0 ; i < interval . size ( ) ; ++ i ) { int start = interval [ i ] . first ; int end = interval [ i ] . second ; vis [ start ] ++ ; vis [ end + 1 ] -- ; } for ( int i = 1 ; i < MAX ; i ++ ) { vis [ i ] += vis [ i - 1 ] ; if ( ! vis [ i ] ) { cout << i << endl ; return ; } } } int main ( ) { vector < pair < int , int > > interval = { { 0 , 14 } , { 86 , 108 } , { 22 , 30 } , { 5 , 17 } } ; find_missing ( interval ) ; return 0 ; }