Find the point where maximum intervals overlap | Program to find maximum guest at any time in a party ; Sort arrival and exit arrays ; guests_in indicates number of guests at a time ; Similar to merge in merge sort to process all events in sorted order ; If next event in sorted order is arrival , increment count of guests ; Update max_guests if needed ; increment index of arrival array ; If event is exit , decrement count ; of guests . ; Driver program to test above function
#include <iostream> NEW_LINE #include <algorithm> NEW_LINE using namespace std ; void findMaxGuests ( int arrl [ ] , int exit [ ] , int n ) { sort ( arrl , arrl + n ) ; sort ( exit , exit + n ) ; int guests_in = 1 , max_guests = 1 , time = arrl [ 0 ] ; int i = 1 , j = 0 ; while ( i < n && j < n ) { if ( arrl [ i ] <= exit [ j ] ) { guests_in ++ ; if ( guests_in > max_guests ) { max_guests = guests_in ; time = arrl [ i ] ; } i ++ ; } else { guests_in -- ; j ++ ; } } cout << " Maximum ▁ Number ▁ of ▁ Guests ▁ = ▁ " << max_guests << " ▁ at ▁ time ▁ " << time ; } int main ( ) { int arrl [ ] = { 1 , 2 , 10 , 5 , 5 } ; int exit [ ] = { 4 , 5 , 12 , 9 , 12 } ; int n = sizeof ( arrl ) / sizeof ( arrl [ 0 ] ) ; findMaxGuests ( arrl , exit , n ) ; return 0 ; }