Getting TLE even though solution in nlogn


#1

I have tried to run the code in a different way using std:: map and total complexity come to be nlogn but getting TLE. I have pasted the full code in C++. Can anybody show the problem with the solution?

Inside one the for loop for every iteration, it’s doing( 3 logn).

1)Log n : for checking any smaller end time in the map of end time
2)log n: remove the element from map.
3)log n: To insert data into the map.

which is n * 3log n = nlogn.

typedef vector vec_1Type;
typedef vector<vec_1Type> vec_2Type;

typedef map<int,int> mapType;

typedef pair<int,int> pairT;

pairT checkAnySmaller(int keyVal , mapType my_map)
{

pairT my_pair;
my_pair.first=false;


mapType::iterator  it = my_map.lower_bound(keyVal);

//If there any end time smaller than the  keyVal.
//else there is overlapping and return true so that new room will be added
if (it != my_map.begin()) {
  it--;
    
    my_pair.first =true;
    my_pair.second= it->first;
    return my_pair;
  
} else {
    
    if(my_map.empty())
        return my_pair;
   
    int val =  it->first;
    
    if(it== my_map.begin() && val <= keyVal )
    {
         my_pair.first=true;
         my_pair.second =  it->first;;
    }
    else
    my_pair.first=false;

    return my_pair;
}


return my_pair;

}

int getMinRoom(vec_2Type & vec){

//Sorted map which will store meeting end time in sorted order
mapType MapEndTime;
int roomCnt = 0;
int len  = vec.size();

//Sort the vector on the basis of start time
sort(vec.begin(), vec.end() );

int delVal = 0;

for(int i=0;i<len;i++)
{
    int curEndT = vec[i][0];
    
    /*Check is there any time end interval smaller than current meeting start time
    /if yes then we need another room
    else
    this meeting can be added into meeting room for smaller end time meeting room
    and erase the smaller end time if its count is less than 1.
    */
    
    //(log n)time to search smaller end time element
    pairT res = checkAnySmaller(curEndT,MapEndTime );
    
    if(res.first ==false)
      {
          roomCnt++;
          
      }      
           
    
    else
    {
        int LowVal = res.second;
        
         MapEndTime[LowVal]--;
        
        
        if(MapEndTime[LowVal] ==0)
            MapEndTime.erase(LowVal);

    
     
        
    }
    
    //Add end time in map which will be in sorted order.
    //(log n) time to insert end time interval
    MapEndTime[vec[i][1]]++;
        
    
}


return roomCnt;

}

int Solution::solve(vector<vector > &A) {

int res= getMinRoom(A);
return res;

}


#2

Although there are much simpler ways to solve this - Using a simple STL sort and proceeding greedily, or using a priority queue. For me they worked and was shorter, sweeter and more intuitive.

Your solution as you described it should still work. I did not check into much details of your algo but one of the red flags I noticed was you forgot to pass the map as a reference variable,

pairT checkAnySmaller(int keyVal , mapType my_map)

my_map should not be passed by value. Once that works, try to make the logic simpler, it would be easier to explain and thereby impress in interviews.