Golang line sweep solution


  • 0

    Until I read this post I really couldn't come up with any solutions.

    The idea is, we keep watching each start time and end time in chronological order. Let's say we have 0 available room first. Whenever a new start time comes, we need a room available. So if available room = 0, we need to increment a total room number we use. Then end time comes, we can release the room for a next meeting, so we need to manage how many rooms currently we have at total and how many are available (or in use).

    The key point is that we really don't need to care about to which meeting start time and end time belongs... hard to come up with this.

    func minMeetingRooms(intervals []Interval) int {
    	ilen := len(intervals)
    	starts, ends := make([]int, ilen), make([]int, ilen)
    	for i, interval := range intervals {
    		starts[i], ends[i] = interval.Start, interval.End
    	}
    	sort.Ints(starts)
    	sort.Ints(ends)
    
    	si, ei := 0, 0
    	roomNum, roomInUse := 0, 0
    	for ei < ilen {
    		if si < ilen && starts[si] < ends[ei] { // start event occurs
    			if roomNum-roomInUse > 0 { // room available
    				roomInUse++
    			} else {
    				roomNum++
    				roomInUse++
    			}
    			si++
    		} else { // end event occurs
    			roomInUse--
    			ei++
    		}
    	}
    	return roomNum
    }
    

Log in to reply
 

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