Swift solution - Binary Search


  • 0
    public class Interval {
        public var start: Int
        public var end: Int
        
        public init(_ start: Int, _ end: Int) {
            self.start = start
            self.end = end
        }
    }
    
    class Solution {
        func findRightInterval(_ intervals: [Interval]) -> [Int] {
            var map = [Int: Int]()
            var starts = [Int]()
            var result = [Int](repeatElement(0, count: intervals.count))
            
            for i in 0..<intervals.count {
                map[intervals[i].start] = i
                starts.append(intervals[i].start)
            }
            starts = starts.sorted()
            for i in 0..<intervals.count {
                let end = intervals[i].end
                let start = binarySearch(starts, end)
                if start < end {
                    result[i] = -1
                } else {
                    result[i] = map[start]!
                }
            }
            
            return result
        }
        
        private func binarySearch(_ nums: [Int], _ target: Int) -> Int {
            var left = 0
            var right = nums.count - 1
            var middle = 0
            
            while left < right {
                middle = (left + right) / 2
                if nums[middle] < target {
                    left = middle + 1
                } else {
                    right = middle
                }
            }
            
            return nums[left]
        }
    }
    

Log in to reply
 

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