[Leetcode] Intervals

Posted on | In , |

Template:
The intersection of two intervals: 

1
2
3
4
5
start = max(a.start, b.start)
end = min(a.end, b.end)
if start <= end:
    # there exist interval
    print(start, end)

252. Meeting Rooms

Leetcode: https://leetcode.com/problems/meeting-rooms/description/

Solution Sort intervals by start first, then see if there’s overlap

1
2
3
4
5
6
7
8
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
    intervals.sort(key = lambda x: x[0])
    if len(intervals) < 2:
        return True
    for i in range(1, len(intervals)):
        if intervals[i - 1][1] > intervals[i][0]:
            return False
    return True

253. Meeting Rooms II

At any point in time we have multiple rooms that can be occupied and we don’t really care which room is free as long as we find one when required for a new meeting.

A naive way to check if a room is available or not is to iterate on all the rooms and see if one is available when we have a new meeting at hand.

1
2
3
4
5
6
7
8
9
10
11
12
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    intervals.sort(key = lambda x: x[0])
    heap = []
    cnt = 0
    for i in range(len(intervals)):
        cur = intervals[i]
        if not heap or heap[0][0] > cur[0]:
            cnt += 1
        else:
            heappop(heap)
        heappush(heap, (cur[1], cur[0]))
    return cnt

452. Minimum Number of Arrows to Burst Balloons

Leetcode: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
Video: https://www.youtube.com/watch?v=DguJN47_mSg&ab_channel=HuaHua

One could always track the end of the current balloon, and ignore all the balloons which end before it. Once the current balloon is ended (= the next balloon starts after the current balloon), one has to increase the number of arrows by one and start to track the end of the next balloon.

1
2
3
4
5
6
7
8
9
10
11
12
13
def findMinArrowShots(self, points: List[List[int]]) -> int:
    if not points:
        return 0
    points.sort(key = lambda x: x[1]) # ? Sort by end
    first_end = points[0][1]
    cnt = 1
    for i in range(1, len(points)):
        if points[i][0] <= first_end:
            continue
        else:
            cnt += 1
            first_end = points[i][1]
    return cnt

56. Merge Intervals

Leetcode: https://leetcode.com/problems/merge-intervals/description/

[Solution] Keep track of the start and end, if start < prev.end, update end to prev.end, else add interval(start, end) to the result list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    List<Interval> res = new ArrayList<Interval>();
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() < 1) return res;
        if (intervals.size() == 1) {
            res.add(intervals.get(0));
            return res;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
           public int compare(Interval a, Interval b) {
               return a.start - b.start;
           }
        });

        int end = intervals.get(0).end;
        int start = intervals.get(0).start;
        Interval prev = null;
        for (Interval cur: intervals) {
            if (cur.start <= end) {
                end = Math.max(cur.end, end);
            } else {
                res.add(new Interval(start, end));
                start = cur.start;
                end = cur.end;
            }
        }
        res.add(new Interval(start, end)); // add the last interval
        return res;
    }
}

57. Insert Interval

Leetcode: https://leetcode.com/problems/insert-interval/description/

Solution:

  1. Before the new Interval, push all the intervals into the output array
  2. Add the new Interval into the output array, if the start of the new interval is smaller than the last tail, merge it with the last one
  3. Add all the intervals after new interval to the output array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        // insert the new interval into the array
        if (intervals == null) return null;
        if (newInterval == null) return intervals;

        List<Interval> res = new ArrayList<Interval>();
        intervals.add(newInterval);
        // sort list by start
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        // merge intervals
        for (Interval curInt: intervals) {
            if (curInt.start <= end) {
                end = Math.max(end,curInt.end);
            } else {
                res.add(new Interval(start, end));
                start = curInt.start;
                end = curInt.end;
            }
        }
        res.add(new Interval(start, end));
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def insert(self, intervals, newInterval):
    """
    :type intervals: List[List[int]]
    :type newInterval: List[int]
    :rtype: List[List[int]]
    """
    if not intervals:
        return [newInterval]
    stack = []
    merge = False
    for i in range(len(intervals)):
        if merge:
            if intervals[i][0] > stack[-1][1]:
                stack.append(intervals[i])
            else:
                stack[-1][1] = max(stack[-1][1], intervals[i][1])
        else:
            if newInterval[0] > intervals[i][1]:
                stack.append(intervals[i])
                continue
            else:
                if newInterval[1] < intervals[i][0]:
                    stack.append(newInterval)
                    stack.append(intervals[i])
                else:
                    stack.append([min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])])
                merge = True
    if not merge:
        stack.append(newInterval)
    return stack

763. Partition Labels

Leetcode: https://leetcode.com/problems/partition-labels/

Note:

  1. Find the start and end point of each unique character
  2. Merge Intervals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def partitionLabels(self, S: str) -> List[int]:
    if not S:
        return []
    intervals = []
    unique = set(S)
    for ch in unique:
        start = S.index(ch)
        end = len(S) - S[::-1].index(ch)
        intervals.append([start, end])
    intervals.sort(key = lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] < merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    res = [a[1] - a[0] for a in merged]
    return res

986. Interval List Intersections

Leetcode: https://leetcode.com/problems/interval-list-intersections/

Solution: Use two pointers to select current intervals in A and B. Move pointer that has a smaller end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var intervalIntersection = function(A, B) {
    let res = [];
    let i = 0;
    let j = 0;
    while (i < A.length && j < B.length) {
        let s = Math.max(A[i][0], B[j][0]);
        let e = Math.min(A[i][1], B[j][1]);
        if (s <= e) {
            res.push([s, e]);
        }
        if (A[i][1] > B[j][1]) { j++ }
        else {i++}
    }
    return res
};

Interval Sum Problem

109. Corporate Flight Bookings

Leetcode: https://leetcode.com/problems/corporate-flight-bookings/

Note: For interval [i, j, k], we need to + k in day i, and would not need k in day j + 1. Thus, we could use an accumulation array for the changes of each day.

1
2
3
4
5
6
7
8
9
def corpFlightBookings(self, bookings, n):
    res = [0] * n
    for b in bookings:
        res[b[0] - 1] += b[2]
        if b[1] < n:
            res[b[1]] -= b[2]
    for i in range(1, len(res)):
        res[i] += res[i - 1]
    return res

Non-overlapping Intervals

630. Course Schedule III

Leetcode: https://leetcode.com/problems/course-schedule-iii/

Leetcode 715. Range Module

Leetcode: https://leetcode.com/problems/range-module/

Video: https://www.youtube.com/watch?v=pcpB9ux3RrQ&ab_channel=HuaHua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class RangeModule:

    def __init__(self):
        self.intervals = []
        
    def addRange(self, left: int, right: int) -> None:
        if not self.intervals:
            self.intervals.append([left, right])
            return
        newIntervals = []
        inserted = False
        for interval in self.intervals:
            # try to merge new interval
            if interval[0] > right and not inserted: # < because right boundary is open
                newIntervals.append([left, right])
                inserted = True
            if interval[1] < left or interval[0] > right:
                newIntervals.append(interval)
            else:
                # try to merge
                left = min(interval[0], left)
                right = max(interval[1], right)
        if not inserted:
            newIntervals.append([left, right])
        self.intervals = newIntervals[::]
            
    def queryRange(self, left: int, right: int) -> bool:
        # binary search for largest start <= left
        l, r = 0, len(self.intervals)
        while l < r - 1:
            mid = (l + r) // 2
            if self.intervals[mid][0] <= left:
                l = mid
            else:
                r = mid
        leftInclude = False
        if l < len(self.intervals) and self.intervals[l][0] <= left and self.intervals[l][1] >= right:
            leftInclude = True
            
        # binary search for the smallest end >= right
        l, r = 0, len(self.intervals)
        while l < r - 1:
            mid = (l + r) // 2
            if self.intervals[mid][1] >= right:
                l = mid
            else:
                r = mid
        rightInclude = False
        if l < len(self.intervals) and self.intervals[l][1] >= right and self.intervals[l][0] <= left:
            rightInclude = True
            
        return leftInclude or rightInclude

    def removeRange(self, left: int, right: int) -> None:
        newIntervals = []
        
        for interval in self.intervals:
            if interval[1] <= left or interval[0] >= right:
                newIntervals.append(interval)
            else:
                if interval[0] < left:
                    newIntervals.append([interval[0], left])
                if interval[1] > right:
                    newIntervals.append([right, interval[1]])
        self.intervals = newIntervals[::]

759. Employee Free Time

Leetcode: https://leetcode.com/problems/employee-free-time/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
    # construct a long list with all the intervals sorted by start
    # since it's sorted, we can use pointers to each schedule lists
    # use prioirty queue to sort
    pointers = [0 for _ in range(len(schedule))]
    fullList = []
    heap = []
    # initialize heap
    for i, p in enumerate(pointers):
            heapq.heappush(heap, (schedule[i][p].start, schedule[i][p].end, i, p))
    while heap:
        start, end, person, pointer = heappop(heap)
        if pointers[person] + 1 < len(schedule[person]):
            
            pointers[person] += 1
            # print(pointers, person)
            curPtr = pointers[person]
            heapq.heappush(heap, (schedule[person][curPtr].start, schedule[person][curPtr].end, person, curPtr))
        
        # merge into fullList
        if not fullList or fullList[-1][1] < start:
            fullList.append([start, end])
        else:
            fullList[-1][1] = max(end, fullList[-1][1])

    # go through the list and find out the gaps
    res = [Interval(-float('inf'), float('inf'))]
    for interval in fullList:
        res[-1].end = interval[0]
        res.append(Interval(interval[1], float('inf')))
    res.pop()
    return res[1:]

Line Sweeping

731. My Calendar II

Leetcode: https://leetcode.com/problems/my-calendar-ii/

  • We will consider ‘start’ time as +1 and ‘end’ time as -1
    • If we currently only have ‘start’ and ‘end’ time
      • The sum between them will equal to 0, which will balance out
    • Now, if we add an overlap between the ‘start/end’ time we will have the following
      • s0, s1, e0, e1
    • Then the sum will be
      • 1 2 1 0
    • Since, there is an overlap, we can see that our highest sum is equal to 2
      • We can continue this approach to 3 or more overlaps
    • Example:
      • s0, s1, s2, e0, e1, e3
      • 1 2 3 2 1 0
    • In this case, our sum has reached 3 and we have found our triple booking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import bisect
class MyCalendarTwo(object):

    def __init__(self):
        self.calendar = []

    def book(self, start, end):
        bisect.insort(self.calendar, (start, 1))
        bisect.insort(self.calendar, (end, -1))
        
        bookings = 0
        for time, freq in self.calendar:
            bookings += freq
            if bookings == 3:
                self.calendar.pop(bisect.bisect_left(self.calendar, (start, 1)))
                self.calendar.pop(bisect.bisect_left(self.calendar, (end, -1)))
                return False
        
        return True

1094. Car Pooling

Leetcode: https://leetcode.com/problems/car-pooling/

1
2
3
4
5
6
7
8
9
10
11
12
13
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    timestamps = []
    for trip in trips:
        timestamps.append([trip[1], trip[0]])
        timestamps.append([trip[2], -trip[0]])
        
    timestamps.sort()
    total = 0
    for t in timestamps:
        total += t[1]
        if total > capacity:
            return False
    return True

Leetcode: 218. The Skyline Problem

Good explanation: https://leetcode.com/problems/the-skyline-problem/discuss/61261/10-line-Python-solution-104-ms/208654

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
    heap = [(0, float('inf'))] # (height, end)
    events = []
    res = [[0, 0]] # (x, height)
    for l, r, h in buildings:
        events.append((l, -h, r))
        events.append((r, 0, 0))
    events.sort()
    for x, negH, end in events:
        while heap[0][1] <= x:
            # pop out all ending buildings
            heappop(heap)
        
        if negH < 0:
            # if a bulding start
            heappush(heap, (negH, end))
            
        if -heap[0][0] != res[-1][1]:
            # meet a new height
            res.append([x, -heap[0][0]])
            
    return res[1:]