Can someone post their Brute Force Solution


  • 0
    L

    Can someone post their Brute Force Solution

    I was able to solve the question in O(nLogn) by sorting the start and end time. However, I can't think of a simple brute force approach to the problem.

    In http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
    It mentions "A Simple Solution is to take every interval one by one and find the number of intervals that overlap with it. Keep track of maximum number of intervals that overlap with an interval. Finally return the maximum value. Time Complexity of this solution is O(n2)."

    But I think it will count the maximum number of overlap during its interval range, but not the minimum at any particular time.
    For example, given input [[0,30],[1,5],[6,10],[11,15],[16,20], [21,25]]
    If we keep track of the max for every interval, the first interval 0 - 30 will overlap with all other 5, so the maximum number of overlapping is 5, but really only 2 rooms are needed to accommodate all meeting.

    Thanks.


Log in to reply
 

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