intervals

• Intervals

  • Greedy: Sort by ending points - Max num of non-overlapping intervals inside a range

    • 757.Set-Intersection-Size-At-Least-Two

  • Greedy: Sort by starting points - Min num of intervals to cover the range

  • Sort either by start or endpoint

  • DP - TODO

  • Sweepline

  • Other

  • Template: Merge interval

    • OPTIONS 1: PriorityQueue

    • OPTIONS 2: Sort intervals by start and merge

    • OPTIONS 3: Sweepline

  • DP: 1235.Maximum-Profit-in-Job-Scheduling

    • Sort by start, based on whether selecting ith job or not

      • Naive implementation: O(N^2)

      • Optimize with binary search: O(NlogN) and zip/unzip

    • Sort by end, based on how many jobs has been completed

    • Greedy

Intervals

Greedy: Sort by ending points - Max num of non-overlapping intervals inside a range

452.Minimum-Number-of-Arrows-to-Burst-Balloons (H-)

435.Non-overlapping-Intervals (M+) (aka. 646.Maximum-Length-of-Pair-Chain)

757.Set-Intersection-Size-At-Least-Two

757.Set-Intersection-Size-At-Least-Two (H)

# Sample Pattern: Two while loop (the return value is the opposite per problem description)
def findLongestChain(self, pairs: List[List[int]]) -> int:
    sortedIn = sorted(pairs, key=lambda x: (x[1], x[0]))
    i = 0
    result = 0
    while i < len(sortedIn):
        j = i + 1
        result += 1
        while j < len(sortedIn) and sortedIn[j][0] <= sortedIn[i][1]:
            j += 1
        i = j
    return result

1751.Maximum-Number-of-Events-That-Can-Be-Attended-II (H)

Greedy: Sort by starting points - Min num of intervals to cover the range

1326.Minimum-Number-of-Taps-to-Open-to-Water-a-Garden (M+)

# Using leetcode 1326 as an example.
def minTaps(self, n: int, ranges: List[int]) -> int:
    intervals = [[i - r, i + r] for i, r in enumerate(ranges)]
    sortedIntervals = sorted(intervals, key=lambda x : (x[0], -x[1])) 
        
    nextEnd = currEnd = currIndex = 0
    numTaps = 0
    while currIndex < len(sortedIntervals) and currEnd < n:
        # for intervals overlapping with current interval,
        # pick the one which has farthest reach
        nextIndex = currIndex
        while nextIndex < len(sortedIntervals) and sortedIntervals[nextIndex][0] <= currEnd:

            # greedily pick the overlapping intervals 
            nextEnd = max(sortedIntervals[nextIndex][1], nextEnd)
            nextIndex += 1
                
        if nextIndex == currIndex:
            return -1
        else:            
            numTaps += 1                
            currIndex = nextIndex
            currEnd = nextEnd
                
    return numTaps if currEnd >= n else -1       

045.Jump-Game-II (M)

1024.Video-Stitching (M+)

Sort either by start or endpoint

1288.Remove-Covered-Intervals (M+)

# using leetcode 1288 as an example
# Greedily pick the interval which has the earliest starting point and biggest length
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:    
    sortedInter = sorted(intervals, key=lambda x: (x[0], -x[1]))
    numRemoved = 0
    currIndex = 0
    while currIndex < len(sortedInter):
        nextStart = currIndex + 1
        while nextStart < len(sortedInter) and sortedInter[nextStart][1] <= sortedInter[currIndex][1]:
           nextStart += 1
           numRemoved += 1
        currIndex = nextStart
    return len(intervals) - numRemoved

DP - TODO

Sweepline

• Split intervals into Pair(int start, boolean isStart), Pair(int end, boolean isEnd)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        boundaryPoints = []
        for interval in intervals:
            boundaryPoints.append((interval[0], 1))
            boundaryPoints.append((interval[1], -1))
        boundaryPoints.sort(key=lambda x: (x[0], -x[1]))

        result = []
        start, end = 0, 0
        count = 0
        for point in boundaryPoints:
            if point[1] == 1:
                count += 1
                if count == 1:
                    start = point[0]
            else:
                count -= 1
                if count == 0:
                    end = point[0]
                    result.append([start, end])

        return result

252.Meeting-Rooms (M) 253.Meeting-Rooms-II (M+) 056.Merge-Intervals (M) 057.Insert-Intervals (M)

1272.Remove-Interval (M+) 252.Meeting-Rooms (M) 253.Meeting-Rooms-II (M+) 056.Merge-Intervals (M) 057.Insert-Intervals (M) 732.My-Calendar-III (M) 759.Employee-Free-Time (M+) 798.Smallest-Rotation-with-Highest-Score (H) 995.Minimum-Number-of-K-Consecutive-Bit-Flips (H-) 1094.Car-Pooling (E) 1109.Corporate-Flight-Bookings (M) 1589.Maximum-Sum-Obtained-of-Any-Permutation (M) 1674.Minimum-Moves-to-Make-Array-Complementary (H) 1871.Jump-Game-VII (M+) 1893.Check if All the Integers in a Range Are Covered (E) 850.Rectangle-Area-II (H) 1943.Describe-the-Painting (H-) 732.My-Calendar-III (M) 759.Employee-Free-Time (M+) 798.Smallest-Rotation-with-Highest-Score (H) 995.Minimum-Number-of-K-Consecutive-Bit-Flips (H-) 1094.Car-Pooling (E) 1109.Corporate-Flight-Bookings (M) 1589.Maximum-Sum-Obtained-of-Any-Permutation (M) 1674.Minimum-Moves-to-Make-Array-Complementary (H) 1871.Jump-Game-VII (M+) 1893.Check if All the Integers in a Range Are Covered (E) 850.Rectangle-Area-II (H) 1943.Describe-the-Painting (H-)

Other

436. Find Right Interval - binary search + map - [TODO]

Template: Merge interval

OPTIONS 1: PriorityQueue

• Here PriorityQueue is also used for sorting purpose but in-house implementation.

• A more complicated solution when compared with OPTIONS 2

OPTIONS 2: Sort intervals by start and merge

• Sort intervals using T/S Complexity: O(nlogn)

sorted(intervals, key=lambda interval: (interval.start, interval.end))

OPTIONS 3: Sweepline

• Count interval start as +1, count interval end as -1

"""
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""
class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        points = []
        for intervalList in schedule:
            for interval in intervalList:
                points.append((interval.start, 1))
                points.append((interval.end, -1))
                
        # when start and end occurs at the same point
        # start should come first
        sortedPoints = sorted(points, key=lambda x: (x[0], -x[1]))
        
        result = []
        counter = 0
        prevPoint = float('-inf')
        for point in sortedPoints:
            if counter == 0 and prevPoint != point[0] and point[0] != point[1] and prevPoint != float('-inf'):
                result.append(Interval(prevPoint, point[0]))
            
            counter = counter + (1 if point[1] == 1 else -1)
            prevPoint = point[0]
        return result

DP: 1235.Maximum-Profit-in-Job-Scheduling

1235.Maximum-Profit-in-Job-Scheduling (H-)

Sort by start, based on whether selecting ith job or not

• https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/733167/Thinking-process-Top-down-DP-Bottom-up-DP

Naive implementation: O(N^2)

# Time limit exceeded
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:        
        # max profit by using from begin to self.end
        @lru_cache(maxsize=None)
        def maxProfit(begin: int) -> int:
            if begin >= self.end:
                return 0
            
            # job at begin
            # take 
            take = self.sortedInter[begin][2]
            for index, zipTuple in enumerate(self.sortedInter[begin+1:], begin+1):
                if zipTuple[0] >= self.sortedInter[begin][1]:
                    take += maxProfit(index)
                    break                    
            
            # not take
            notTake = maxProfit(begin + 1)            

            return max(take, notTake)
        
        self.sortedInter = sorted(zip(startTime, endTime, profit))
        self.end = len(self.sortedInter)
        return maxProfit(0)

Optimize with binary search: O(NlogN) and zip/unzip

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:        
        # max profit by using from pos to self.end - 1
        @lru_cache(maxsize=None)
        def maxProfit(pos: int) -> int:
            if pos >= self.end:
                return 0
            
            # job at pos
            # take 
            take = self.sortedProfit[pos]
            index = bisect.bisect_left(self.sortedStart, self.sortedEnd[pos], pos + 1)
            take += maxProfit(index)
                
            # not take
            notTake = maxProfit(pos + 1)            

            return max(take, notTake)
        
        self.sortedStart, self.sortedEnd, self.sortedProfit = zip(*sorted(zip(startTime, endTime, profit)))
        self.end = len(self.sortedStart)
        return maxProfit(0)

Sort by end, based on how many jobs has been completed

• https://github.com/wisdompeak/LeetCode/tree/master/Greedy/1235.Maximum-Profit-in-Job-Scheduling

• Similar thought as above

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        
        # maximum profit from 0 to pos
        @lru_cache(maxsize=None)
        def maxProfit(pos: int) -> int:
            if pos < 0:
                return 0
                        
            notTake = maxProfit(pos - 1)
            take = self.sortedProfit[pos]            

            # here need to use bisect_right
            index = bisect.bisect_right(self.sortedEnd, self.sortedStart[pos])
            take += maxProfit(index - 1)
            
            return max(take, notTake)
        
        self.sortedEnd, self.sortedStart, self.sortedProfit = zip(*sorted(zip(endTime, startTime, profit)))
        return maxProfit(len(self.sortedEnd) - 1)

Greedy

• Interval + DP + Binary search

• TODO

  • Use named tuples

  • Limitations of lru_cache

  • Sorted() key word