Interval List Intersections LeetCode solution in Python

1
# Runtime: 325 ms (Top 13.56%) | Memory: 15.2 MB (Top 15.52%)
2
from collections import deque
3

4

5
class Solution:
6
    def intervalIntersection(
7
        self, firstList: List[List[int]], secondList: List[List[int]]
8
    ) -> List[List[int]]:
9

10
        answer = []
11

12
        if len(firstList) == 0 or len(secondList) == 0:
13
            return answer
14

15
        first_queue = deque(firstList)
16
        second_queue = deque(secondList)
17

18
        first = first_queue.popleft()
19
        second = second_queue.popleft()
20

21
        while first_queue or second_queue:
22

23
            if first[1] < second[0]:
24
                if len(first_queue):
25
                    first = first_queue.popleft()
26
                    continue
27
                break
28
            if second[1] < first[0]:
29
                if len(second_queue) > 0:
30
                    second = second_queue.popleft()
31
                    continue
32
                break
33

34
            if first[0] <= second[0] and second[0] <= first[1]:
35
                if first[1] <= second[1]:
36
                    answer.append([second[0], first[1]])
37
                    if len(first_queue) > 0:
38
                        first = first_queue.popleft()
39
                        continue
40
                    break
41

42
                else:
43
                    answer.append(second)
44
                    if len(second_queue) > 0:
45
                        second = second_queue.popleft()
46
                        continue
47
                    break
48
            if second[0] <= first[0] and first[0] <= second[1]:
49
                if second[1] <= first[1]:
50
                    answer.append([first[0], second[1]])
51
                    if len(second_queue) > 0:
52
                        second = second_queue.popleft()
53
                        continue
54
                    break
55

56
                else:
57
                    answer.append(first)
58
                    if len(first_queue) > 0:
59
                        first = first_queue.popleft()
60
                        continue
61
                    break
62

63
        if first[0] <= second[0] and second[0] <= first[1]:
64
            if first[1] <= second[1]:
65

66
                if len(answer) > 0:
67

68
                    if answer[-1] != [second[0], first[1]]:
69
                        answer.append([second[0], first[1]])
70
                elif not answer:
71
                    answer.append([second[0], first[1]])
72
            else:
73
                if len(answer) > 0:
74
                    if answer[-1] != second:
75
                        answer.append(second)
76
                elif not answer:
77
                    answer.append(second)
78
        elif second[0] <= first[0] and first[0] <= second[1]:
79
            if second[1] <= first[1]:
80
                if len(answer) > 0:
81
                    if answer[-1] != [first[0], second[1]]:
82
                        answer.append([first[0], second[1]])
83
                elif not answer:
84
                    answer.append([first[0], second[1]])
85
            else:
86
                if len(answer) > 0:
87
                    if answer[-1] != first:
88
                        answer.append(first)
89
                elif not answer:
90

91
                    answer.append(first)
92

93
        return answer