Solution For Interval List Intersections
Problem description:
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.
The intersection of two closed intervals is a set of real numbers that is either empty or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Solution:
The problem can be solved by iterating through both the lists simultaneously, and computing the intersection of the current interval pairs.
To compute the intersection of two intervals, we take the maximum of their start points as the start point of the intersection interval, and the minimum of their end points as the end point of the intersection interval.
We maintain two pointers, i and j, for the two lists. We also maintain an empty list, result, to store the intersection intervals.
We iterate as long as i and j are within their bounds. If the current interval pairs (firstList[i], secondList[j]) intersect, we append the intersection interval to the result list. We then increment the pointer for the interval that ends the earliest. If the current interval pairs do not intersect, we increment the pointer for the interval that ends the earliest.
Once we have finished iterating through the lists, we return the result list.
Here is the Python implementation:
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
result = []
while i < len(firstList) and j < len(secondList):
start = max(firstList[i][0], secondList[j][0])
end = min(firstList[i][1], secondList[j][1])
if start <= end:
result.append([start, end])
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return result
Time Complexity: O(m+n), where m and n are the lengths of the two input lists.
Space Complexity: O(1), as we are only using constant space to keep track of pointers and result list.
Step by Step Implementation For Interval List Intersections
/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ class Solution { public Interval[] intervalIntersection(Interval[] A, Interval[] B) { // check for empty inputs if (A == null || A.length == 0 || B == null || B.length == 0) { return new Interval[0]; } // create a list to store the results Listresult = new ArrayList<>(); // pointers to keep track of the current interval in each array int i = 0, j = 0; // while the pointers have not reached the end of either array while (i < A.length && j < B.length) { // find the interval with the smaller start time Interval a = A[i]; Interval b = B[j]; if (a.start <= b.start) { // if the end time of the interval with the smaller start time is greater than or equal to the other interval's start time // then there is an intersection if (a.end >= b.start) { // create a new interval with the maximum start time and the minimum end time result.add(new Interval(Math.max(a.start, b.start), Math.min(a.end, b.end))); } // if the end time of the interval with the smaller start time is less than the other interval's start time // then move on to the next interval in the array with the smaller start time else { i++; } } // if the start time of the interval with the smaller start time is greater than the other interval's start time // then move on to the next interval in the array with the greater start time else { j++; } } // convert the list to an array and return return result.toArray(new Interval[result.size()]); } }
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].) Example 1: Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists. Note: 0 <= A.length < 1000 0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9 NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature. # Python Solution class Solution: def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]: # create empty list to store results result = [] # set two pointers, i and j, to keep track of the current interval in each list i = 0 j = 0 # iterate through the intervals in A and B # while both pointers are less than the length of their respective lists while i < len(A) and j < len(B): # find the start and end of the intersection of A[i] and B[j] # this is done by taking the maximum of the start of A[i] and B[j] # and taking the minimum of the end of A[i] and B[j] start = max(A[i][0], B[j][0]) end = min(A[i][1], B[j][1]) # if the start is less than or equal to the end, this means that there is an intersection if start <= end: # add the intersection to the result list result.append([start, end]) # if the end of A[i] is less than the end of B[j], increment i # this is because A[i] ends before B[j], so there can't be any more intersections with B[j] # we must check the next interval in A if A[i][1] < B[j][1]: i += 1 # else, the end of B[j] is less than the end of A[i], so we increment j else: j += 1 return result
/** * @param {number[][]} A * @param {number[][]} B * @return {number[][]} */ var intervalIntersection = function(A, B) { // result will store the output let result = []; // i and j are used as pointers for the respective arrays let i = 0; let j = 0; // while loop to iterate through both the arrays while(i < A.length && j < B.length) { // find the starting point of the intersection let start = Math.max(A[i][0], B[j][0]); // find the ending point of the intersection let end = Math.min(A[i][1], B[j][1]); // if start is less than end, it means there is an intersection // push the intersection into the result array if(start <= end) { result.push([start, end]); } // if the ending of the first array is less than the second array, // it means the first array is finished and we need to move to the next element in the second array if(A[i][1] < B[j][1]) { i++; } // else if the ending of the second array is less than the first array, // it means the second array is finished and we need to move to the next element in the first array else if(A[i][1] > B[j][1]) { j++; } // else if the ending of both the arrays is equal, // it means we need to move to the next element in both the arrays else { i++; j++; } } return result; };
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: vectorintervalIntersection(vector & A, vector & B) { int i=0,j=0; vector result; while(i Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].) Example 1: Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists. Note: 0 <= A.length < 1000 0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9 NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature. public class Solution { public int[][] IntervalIntersection(int[][] A, int[][] B) { } }