Minimum Platforms(Greedy Standard Problem)

I’ve been trying hard to solve the minimum platforms problem on geeksforgeeks platform . I’ve come up with a solution using priority Queue but my solution is failing for 5 cases(All of length 50000). I just want to know where my solution is failing. Please help me. I’m new to DSA

Edit :- I’ve even tried stress testing, yet I couldn’t find a case where my code fails.

Here’s the problem link :
https://practice.geeksforgeeks.org/problems/minimum-platforms-1587115620/1#

Here’s my Solution :

struct Interval{
      
      int arrival;
      int departure;
      int platform;    
        
    };
    
 
        bool comp(Interval I1, Interval I2)
    {
        if(I1.arrival == I2.arrival)
            return I1.departure < I2.departure;
        
        else
            return I1.arrival < I2.arrival;
        
    }
 class Solution{
     
  public:
    int findPlatform(int arr[], int dep[], int n)
    {
        
        vector<Interval> I(n);
        priority_queue<int, vector<int>, greater<int>> platforms;
        for(int i = 0; i < n; i++)
        {
            I[i].arrival = arr[i];
            I[i].departure = dep[i];
            I[i].platform = 0;
            
        }
        
        sort(I.begin(), I.end(), comp);
        
    
        
        //vector<int> platforms;
        
        platforms.push(I[0].departure);
        for(int i = 1; i < n; i++)
        {
            int top = platforms.top();
            
            if(top < I[i].arrival)
                platforms.pop();
           platforms.push(I[i].departure);
            
           
        }
        
        return platforms.size();
    }
};

try to use long long maybe that work or their is standard way use map<int,char>
give arrival time value ‘a’ and departure time ‘d’ and just traverse over map and see which concides

By the constraints the maximum value of the platforms should not exceed 50000. That’s the reason I’m not using long long .

you just need to replace your ‘if’ with ‘while’ .(in that last for loop)

1 Like