LeetCode Solutions

986. Interval List Intersections

Time: $O(n)$

Space: $O(n)$

			

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;
  }
};
			

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()][]);
  }
}
			

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