Simple C solution (nlogn), 2 qsorts and 1 pass


  • 0
    int cmpfunc2 (const void * a, const void * b)
    {
       return ( ((struct Interval*)a)->end - ((struct Interval*)b)->end);
    }
    
    int cmpfunc (const void * a, const void * b)
    {
       return ( ((struct Interval*)a)->start - ((struct Interval*)b)->start);
    }
    
    int minMeetingRooms(struct Interval* intervals, int intervalsSize) {
       int i,count=intervalsSize,j;
       qsort(intervals, intervalsSize, sizeof(struct Interval), cmpfunc);
       struct Interval* ca = malloc((intervalsSize)*sizeof(struct Interval));
       memcpy(ca,intervals,(intervalsSize)*sizeof(sizeof(struct Interval)));
       qsort(ca, intervalsSize, sizeof(struct Interval), cmpfunc2);
    
       if(!intervalsSize)
         return 0;
        
       for(i=0;i<intervalsSize;i++)
       {
           for(j=0;j<intervalsSize;j++)
           {
               if((intervals[i].start >= ca[j].end) && (ca[j].end!=-1))
               {
                   ca[j].end = -1;
                   count--;
                   break;
               }
           }
       }
    
      return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.