Interval List Intersections

Slug: interval-list-intersections

Difficulty: Medium

Id: 891250

Topic Tags: two-pointer-algorithm, Arrays, Data Structures, Algorithms

Company Tags: Bloomberg, Amazon, Microsoft, Google, Uber

Summary

Given a list of intervals, where each interval is represented as a pair of integers (start, end), the problem involves finding all intersections between these intervals. An intersection occurs when the start value of one interval is greater than or equal to the end value of another interval. The goal is to return all such intersections in sorted order.

Detailed Explanation

To solve this problem, we can use a two-pointer approach. We initialize two pointers, one at the start of each interval list. We then iterate through both lists simultaneously, comparing the current intervals at the pointer positions.

Here's a step-by-step breakdown of the solution:

Initialize two pointers, i and j, to the start of each interval list.
Compare the current intervals at positions i and j. If they intersect (i.e., the start value of one interval is greater than or equal to the end value of another), add the intersection to the result list.
Move the pointer with the smaller end value forward, as all remaining intervals in that list will also be considered for intersections.
Repeat steps 2-3 until one of the lists is exhausted.

Time complexity: O(n + m), where n and m are the lengths of the interval lists. Space complexity: O(k), where k is the number of intersections found.

Optimized Solutions

Java

import java.util.*; public class IntervalListIntersections { public static List<List<int[]>> findIntersections(int[][] intervals1, int[][] intervals2) { List<List<int[]>> result = new ArrayList<>(); // Initialize pointers for both lists int i = 0, j = 0; while (i < intervals1.length && j < intervals2.length) { if (intervals1[i][1] >= intervals2[j][0]) { // Add intersection to result list List<int[]> intersection = new ArrayList<>(); intersection.add(intervals1[i]); intersection.add(intervals2[j]); result.add(intersection); // Move pointer with smaller end value forward if (intervals1[i][1] < intervals2[j][1]) { i++; } else { j++; } } else if (intervals1[i][0] > intervals2[j][1]) { // Move pointer for list 1 forward i++; } else { // Move pointer for list 2 forward j++; } } return result; } }