Skip to content

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<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                           vector<vector<int>>& secondList) {
    vector<vector<int>> 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<int[]> 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
20
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