Interval Problem

Algorithms
topic
Catalogue
  1. 1. Range
    1. 1.1. 370. Range Addition
  2. 2. Overlap
    1. 2.1. 252. Meeting Rooms
    2. 2.2. 253. Meeting Rooms II
  3. 3. Operations
    1. 3.1. 56. Merge Intervals
    2. 3.2. 57. Insert Interval

Range

370. Range Addition

Trade off for Update and Query!

  • O(1) for update and O(n) for Query
  • O(n) for update and O(1) for Query
  • We only care about the intervals start and end!!!
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def getModifiedArray(self, length, updates):
        nums = [0] * length
        for start, end, diff in updates:
            nums[start] += diff
            if end < length - 1:
                nums[end+1] -= diff

        for i in range(1, length):
            nums[i] += nums[i-1]
        return nums

Overlap

  • How to define two intervals overapped?
  1. A.end > B.start
  2. B.end > A.start
  • Why we always sort by start or end at first?

    252. Meeting Rooms

    1
    2
    3
    4
    5
    6
    7
    class Solution:
        def canAttendMeetings(self, intervals):
            intervals.sort(key=lambda x:x.start)
            for i in range(1, len(intervals)):
                if intervals[i].start < intervals[i-1].end:
                    return False
            return True

253. Meeting Rooms II

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def minMeetingRooms(self, intervals):
        times = []
        for interval in intervals:
            times.append((interval.start, 1))
            times.append((interval.end, 0))
        times.sort()
        res = 0
        cnt = 0
        for time, fg in times:
            cnt += 1 if fg == 1 else -1
            res = max(res, cnt)
        return res
  • Follow Up : Return Max Overlapped Interval

Operations

56. Merge Intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        if not intervals:
            return []

        intervals.sort(key = lambda x:x.start)
        n = len(intervals)
        stack = [intervals[0]]
        for i in range(1, n):
            start, end = intervals[i].start, intervals[i].end
            if start <= stack[-1].end:
                stack[-1].end = max(stack[-1].end, end)
            else:
                stack.append(intervals[i])
        return stack

57. Insert Interval

  • O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution(object):
        def insert(self, intervals, newInterval):
            n = len(intervals)
            res = []
            i = 0
            while i < n and newInterval.start > intervals[i].end:
                res.append(intervals[i])
                i += 1

            while i < n and intervals[i].start <= newInterval.end:
                newInterval.start = min(intervals[i].start, newInterval.start)
                newInterval.end = max(intervals[i].end, newInterval.end)
                i += 1
            res.append(newInterval)

            while i < n:
                res.append(intervals[i])
                i += 1

            return res
Share