# 986. Interval List Intersections

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: vector> intervalIntersection(vector>& firstList, vector>& secondList) { vector> ans; short i = 0; short j = 0; while (i < firstList.size() && j < secondList.size()) { // Lo := the start of the intersection // Hi := the end of the intersection const int lo = max(firstList[i][0], secondList[j][0]); const int hi = min(firstList[i][1], secondList[j][1]); if (lo <= hi) ans.push_back({lo, hi}); firstList[i][1] < secondList[j][1] ? ++i : ++j; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int[][] intervalIntersection(int[][] firstList, int[][] secondList) { List ans = new ArrayList<>(); short i = 0; short j = 0; while (i < firstList.length && j < secondList.length) { // Lo := the start of the intersection // Hi := the end of the intersection final int lo = Math.max(firstList[i][0], secondList[j][0]); final int hi = Math.min(firstList[i][1], secondList[j][1]); if (lo <= hi) ans.add(new int[] {lo, hi}); if (firstList[i][1] < secondList[j][1]) ++i; else ++j; } return ans.toArray(new int[ans.size()][]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]: ans = [] i = 0 j = 0 while i < len(firstList) and j < len(secondList): # Lo := the start of the intersection # Hi := the end of the intersection lo = max(firstList[i][0], secondList[j][0]) hi = min(firstList[i][1], secondList[j][1]) if lo <= hi: ans.append([lo, hi]) if firstList[i][1] < secondList[j][1]: i += 1 else: j += 1 return ans