Interval List Intersections

MediumIntervalstwo pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two lists of closed intervals, firstList and secondList. Within each list the intervals are sorted by start and pairwise disjoint (no two share even an endpoint). Interval [a, b] covers every real number x with a <= x <= b. Return the intersection of the two lists: every maximal interval of points covered by both lists. A single shared point counts and is returned as [x, x]. Return the intervals sorted by start. If the lists never overlap, return []. Aim for O(n + m) time.

Examples

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]]
For example [5,10] and [1,5] share only the point 5, and [13,23] and [15,24] share [15,23].
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
An empty list intersects with nothing.

Constraints

  • 0 <= firstList.length, secondList.length <= 1000
  • 0 <= start_i <= end_i <= 10^9
  • end_i < start_{i+1} within each list

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More two pointers problems