Saturday, 20 April 2013

Given a list of ranges and provide anew range and find missing ranges coming in between the newly provided range. For example if you have ranges [5,10], [15,19], [ 17,24] and provide a new range [3,28] . Missing ranges are [3,4],[11,14] and [25,28].

#include<iostream>
#include<map>
#include<utility>
#include<conio.h>
using namespace std;
typedef pair<int,int> int_pair;
int main()
{
    map<int,int> myMap;
    myMap.insert(int_pair(6,10));
    myMap.insert(int_pair(15,19));
    myMap.insert(int_pair(17,24));

    int_pair new1(3,25);
    typedef map<int,int>::iterator it_myMap;
    int left=new1.first;
    int right=0;
    map<int,int>  result;
    int val=0;
    for(it_myMap it =myMap.begin();  it!=myMap.end(); ++it)
    {
        if(((it->first) - left )> 1)
        {
           val=it->first;       
           right= --(val);
           result.insert(int_pair(left,right));
           left=++(it->second);
          
        }
        else
           left= ++(it->second);
    }
    it_myMap it= --(myMap.end());
    if(it->second < new1.second)
       result.insert(int_pair((it->second), new1.second));
    cout<<result.size()<<endl;
   
    for(it_myMap it =result.begin();  it!=result.end(); ++it)
    {
         cout<<it->first<<" "<<it->second<<endl;
    }
    getch();
         
}

No comments:

Post a Comment