ac solution code


  • 0
        /*
         Solution1. Non-Heap: Segment Two Pointers + HashMap
         Time  = O(nlgn) = n(for loop) + nlgn(Sort) + n(for loop)
         Space = O(n)
    
         The basic idea is using Two pointers/HashMap to store the room changes at each timePoint(start or end):
    
         Start timePoint: change + 1
         End   timePoint: change - 1
         Then sort the timePoints in the ascending order, sum the changes of each timePoint, output the maximum sum as the result
         (A tricky situation is, if start[i] equals end[j], then we should count the end first, otherwise 1 extra room will be counted. HashMap solution can solve this problem, because changes of each timePoint is already the sum calculation result of all start changes and end changes in that timePoint, no order needed.)
         */
        func minMeetingRooms(_ intervals: [Interval]) -> Int {
            let starts = intervals.map{$0.start}.sorted()
            let ends = intervals.map{$0.end}.sorted()
            var i = 0, j = 0, count = 0 // starts: i; ends: j
    
            while i < starts.count && j < ends.count {// Two pointers
                if starts[i] < ends[j] {// <-- ends[j]
                    count += 1  // Conflicts: count++
                    i += 1      // Forward: start, if conflicts
                } else {        // Forward: start/end
                    i += 1
                    j += 1
                }
            }
    
            return count
        }
    

    0_1503897890428_Screen Shot 2017-08-27 at 10.24.18 PM.png


Log in to reply
 

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