Javascript code sharing without heap


  • 0
    Y
    var minMeetingRooms = function(intervals) {
        var sortByStart = function(interval1, interval2) {
            if (interval1.start < interval2.start) {
                return -1;
            } else if (interval1.start === interval2.start) {
                return 0;
            } else {
                return 1;
            }
        };
        var findRoom = function(rooms, interval) {
            var n = rooms.length;
            var i = 0;
            for (; i < n; i+=1) {
                if (rooms[i] <= interval.start) {
                    return i;
                }
            }
            return n;
        };
        var rooms = [];
        var n = intervals.length;
        var i = 0, roomIndex;
        intervals.sort(sortByStart);
        for (; i < n; i += 1) {
            // find an existing room. create a new one when necessary
            roomIndex = findRoom(rooms, intervals[i]);
            rooms[roomIndex] = intervals[i].end;
        }
        return rooms.length;
    };
    

    findRoom function can be optimized by using a min heap on the end time. But javascript doesn't have heap data structure so I have to scan through each existing room.


Log in to reply
 

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