# intervals

* [Intervals](#intervals)
  * [Greedy: Sort by ending points - Max num of non-overlapping intervals inside a range](#greedy-sort-by-ending-points---max-num-of-non-overlapping-intervals-inside-a-range)
    * [757.Set-Intersection-Size-At-Least-Two](#757set-intersection-size-at-least-two)
  * [Greedy: Sort by starting points - Min num of intervals to cover the range](#greedy-sort-by-starting-points---min-num-of-intervals-to-cover-the-range)
  * [Sort either by start or endpoint](#sort-either-by-start-or-endpoint)
  * [DP - TODO](#dp---todo)
  * [Sweepline](#sweepline)
  * [Other](#other)
  * [Template: Merge interval](#template-merge-interval)
    * [OPTIONS 1: PriorityQueue](#options-1-priorityqueue)
    * [OPTIONS 2: Sort intervals by start and merge](#options-2-sort-intervals-by-start-and-merge)
    * [OPTIONS 3: Sweepline](#options-3-sweepline)
  * [DP: 1235.Maximum-Profit-in-Job-Scheduling](#dp-1235maximum-profit-in-job-scheduling)
    * [Sort by start, based on whether selecting ith job or not](#sort-by-start-based-on-whether-selecting-ith-job-or-not)
      * [Naive implementation: O(N^2)](#naive-implementation-on2)
      * [Optimize with binary search: O(NlogN) and zip/unzip](#optimize-with-binary-search-onlogn-and-zipunzip)
    * [Sort by end, based on how many jobs has been completed](#sort-by-end-based-on-how-many-jobs-has-been-completed)
    * [Greedy](#greedy)

## Intervals

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

[452.Minimum-Number-of-Arrows-to-Burst-Balloons](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/452.Minimum-Number-of-Arrows-to-Burst-Balloons) (H-)

[435.Non-overlapping-Intervals](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/435.Non-overlapping-Intervals) (M+) (aka. [646.Maximum-Length-of-Pair-Chain](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/646.Maximum-Length-of-Pair-Chain))

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

[757.Set-Intersection-Size-At-Least-Two](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/757.Set-Intersection-Size-At-Least-Two) (H)

```python
# 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](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/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](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/1326.Minimum-Number-of-Taps-to-Open-to-Water-a-Garden) (M+)

```python
# 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](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/045.Jump-Game-II) (M)

[1024.Video-Stitching](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/1024.Video-Stitching) (M+)

### Sort either by start or endpoint

[1288.Remove-Covered-Intervals](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/1288.Remove-Covered-Intervals) (M+)

```python
# 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)

```python
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](https://github.com/wisdompeak/LeetCode/tree/master/Others/252.Meeting-Rooms) (M)\
[253.Meeting-Rooms-II](https://github.com/wisdompeak/LeetCode/tree/master/Others/253.Meeting-Rooms-II) (M+)\
[056.Merge-Intervals](https://github.com/wisdompeak/LeetCode/tree/master/Others/056.Merge-Intervals) (M)\
[057.Insert-Intervals](https://github.com/wisdompeak/LeetCode/tree/master/Others/057.Insert-Interval) (M)

[1272.Remove-Interval](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/1272.Remove-Interval) (M+) [252.Meeting-Rooms](https://github.com/wisdompeak/LeetCode/tree/master/Others/252.Meeting-Rooms) (M)\
[253.Meeting-Rooms-II](https://github.com/wisdompeak/LeetCode/tree/master/Others/253.Meeting-Rooms-II) (M+)\
[056.Merge-Intervals](https://github.com/wisdompeak/LeetCode/tree/master/Others/056.Merge-Intervals) (M)\
[057.Insert-Intervals](https://github.com/wisdompeak/LeetCode/tree/master/Others/057.Insert-Interval) (M)\
[732.My-Calendar-III](https://github.com/wisdompeak/LeetCode/tree/master/Others/732.My-Calendar-III) (M)\
[759.Employee-Free-Time](https://github.com/wisdompeak/LeetCode/tree/master/Others/759.Employee-Free-Time) (M+)\
[798.Smallest-Rotation-with-Highest-Score](https://github.com/wisdompeak/LeetCode/tree/master/Others/798.Smallest-Rotation-with-Highest-Score) (H)\
[995.Minimum-Number-of-K-Consecutive-Bit-Flips](https://github.com/wisdompeak/LeetCode/tree/master/Others/995.Minimum-Number-of-K-Consecutive-Bit-Flips) (H-)\
[1094.Car-Pooling](https://github.com/wisdompeak/LeetCode/tree/master/Others/1094.Car-Pooling) (E)\
[1109.Corporate-Flight-Bookings](https://github.com/wisdompeak/LeetCode/tree/master/Others/1109.Corporate-Flight-Bookings) (M)\
[1589.Maximum-Sum-Obtained-of-Any-Permutation](https://github.com/wisdompeak/LeetCode/tree/master/Others/1589.Maximum-Sum-Obtained-of-Any-Permutation) (M)\
[1674.Minimum-Moves-to-Make-Array-Complementary](https://github.com/wisdompeak/LeetCode/tree/master/Others/1674.Minimum-Moves-to-Make-Array-Complementary) (H)\
[1871.Jump-Game-VII](https://github.com/wisdompeak/LeetCode/tree/master/Others/1871.Jump-Game-VII) (M+)\
1893.Check if All the Integers in a Range Are Covered (E)\
[850.Rectangle-Area-II](https://github.com/wisdompeak/LeetCode/tree/master/Others/850.Rectangle-Area-II) (H)\
[1943.Describe-the-Painting](https://github.com/wisdompeak/LeetCode/tree/master/Others/1943.Describe-the-Painting) (H-)\
[732.My-Calendar-III](https://github.com/wisdompeak/LeetCode/tree/master/Others/732.My-Calendar-III) (M)\
[759.Employee-Free-Time](https://github.com/wisdompeak/LeetCode/tree/master/Others/759.Employee-Free-Time) (M+)\
[798.Smallest-Rotation-with-Highest-Score](https://github.com/wisdompeak/LeetCode/tree/master/Others/798.Smallest-Rotation-with-Highest-Score) (H)\
[995.Minimum-Number-of-K-Consecutive-Bit-Flips](https://github.com/wisdompeak/LeetCode/tree/master/Others/995.Minimum-Number-of-K-Consecutive-Bit-Flips) (H-)\
[1094.Car-Pooling](https://github.com/wisdompeak/LeetCode/tree/master/Others/1094.Car-Pooling) (E)\
[1109.Corporate-Flight-Bookings](https://github.com/wisdompeak/LeetCode/tree/master/Others/1109.Corporate-Flight-Bookings) (M)\
[1589.Maximum-Sum-Obtained-of-Any-Permutation](https://github.com/wisdompeak/LeetCode/tree/master/Others/1589.Maximum-Sum-Obtained-of-Any-Permutation) (M)\
[1674.Minimum-Moves-to-Make-Array-Complementary](https://github.com/wisdompeak/LeetCode/tree/master/Others/1674.Minimum-Moves-to-Make-Array-Complementary) (H)\
[1871.Jump-Game-VII](https://github.com/wisdompeak/LeetCode/tree/master/Others/1871.Jump-Game-VII) (M+)\
1893.Check if All the Integers in a Range Are Covered (E)\
[850.Rectangle-Area-II](https://github.com/wisdompeak/LeetCode/tree/master/Others/850.Rectangle-Area-II) (H)\
[1943.Describe-the-Painting](https://github.com/wisdompeak/LeetCode/tree/master/Others/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

```python
"""
# 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](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/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)**

```python
# 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**

```python
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

```python
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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://eric-zhang-seattle.gitbook.io/leetcode-1/data-structures/intervals.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.