Concise JavaScript O(n log n) similar to parentheses


  • 0
    var minMeetingRooms = function(intervals) {
        const times = [];
        for (let int of intervals) {
            times.push([int.start, 1], [int.end, -1]);
        }
        times.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
        let rooms = 0;
        return times.reduce((max, pair) => Math.max(max, rooms += pair[1]), 0);
    };
    
    1. Sort times as if arranging opening and closing parentheses, preferring closing when they happen at the same time (since the meeting room will free up).
    2. Walk through counting the unclosed parenthetical blocks, taking the maximum seen.

    Here's a much slower (due to concat) one-liner:

    var minMeetingRooms = function(intervals, rooms = 0) {
        return intervals
            .reduce((times, int) => times.concat([[int.start, 1], [int.end, -1]]), [])
            .sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])
            .reduce((max, pair) => Math.max(max, rooms += pair[1]), 0);
    };
    

Log in to reply
 

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