Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonGoogle

Interval List Intersections

Choose your preparation mode4 modes available
🎯
Interval List Intersections
mediumINTERVALSFacebookAmazonGoogle

Imagine two friends each have their own schedule of busy time slots, and you want to find all the times when both are busy simultaneously.

💡 This problem involves understanding how to find overlapping intervals between two lists. Beginners often struggle because it requires careful pointer movement and interval comparisons, which can be tricky without a clear approach.
📋
Problem Statement

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. Each intersection is a closed interval that represents the overlapping time between intervals from the two lists.

1 ≤ number of intervals in each list ≤ 10^5Intervals are sorted by start time and do not overlap within the same listInterval start and end values are integers within a valid range
💡
Example
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]]

We find all overlapping intervals by comparing intervals from A and B and collecting their intersections.

  • One or both lists are empty → output is empty list
  • Intervals that touch at a single point (e.g., [1,2] and [2,3]) → intersection is that single point [2,2]
  • One list has intervals completely before or after the other list → no intersections
  • Intervals with the same start and end (single-point intervals) → handled correctly
⚠️
Common Mistakes
Not advancing pointers correctly

Infinite loop or missed intersections

✅ Always advance the pointer with the smaller interval end

Incorrect overlap condition (using < instead of <=)

Misses intersections where intervals touch at a point

✅ Use start <= end to include touching intervals

Assuming intervals within the same list can overlap

Incorrect results or complexity assumptions

✅ Remember problem states intervals are disjoint within each list

Not handling empty input lists

Runtime errors or incorrect output

✅ Check for empty lists before processing

Appending intervals without checking overlap

Incorrect intervals in output

✅ Check if start <= end before appending

🧠
Brute Force (Nested Loops)
💡 This approach exists to build intuition by checking every possible pair of intervals, which helps understand the problem deeply before optimizing.

Intuition

Compare every interval in list A with every interval in list B to find overlaps. If intervals overlap, record the intersection.

Algorithm

  1. Initialize an empty result list.
  2. For each interval in list A, iterate through all intervals in list B.
  3. Check if the two intervals overlap by comparing their start and end points.
  4. If they overlap, compute the intersection and add it to the result list.
💡 Nested loops make it easy to understand but inefficient; it's a direct translation of the problem statement.
</>
Code
from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    result = []
    for i in range(len(A)):
        for j in range(len(B)):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            if start <= end:
                result.append([start, end])
    return result

# Driver code
if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))
Line Notes
result = []Initialize list to store intersections
for i in range(len(A))Outer loop iterates over intervals in A
for j in range(len(B))Inner loop iterates over intervals in B
start = max(A[i][0], B[j][0])Find the later start time between two intervals
end = min(A[i][1], B[j][1])Find the earlier end time between two intervals
if start <= endCheck if intervals overlap
result.append([start, end])Add the overlapping interval to result
import java.util.*;

public class IntervalIntersection {
    public static List<int[]> intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int start = Math.max(A[i][0], B[j][0]);
                int end = Math.min(A[i][1], B[j][1]);
                if (start <= end) {
                    result.add(new int[]{start, end});
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] A = {{0,2},{5,10},{13,23},{24,25}};
        int[][] B = {{1,5},{8,12},{15,24},{25,26}};
        List<int[]> res = intervalIntersection(A, B);
        for (int[] interval : res) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}
Line Notes
List<int[]> result = new ArrayList<>();Create list to store intersections
for (int i = 0; i < A.length; i++)Outer loop over intervals in A
for (int j = 0; j < B.length; j++)Inner loop over intervals in B
int start = Math.max(A[i][0], B[j][0]);Later start time between intervals
int end = Math.min(A[i][1], B[j][1]);Earlier end time between intervals
if (start <= end)Check if intervals overlap
result.add(new int[]{start, end});Add intersection to result
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> result;
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            if (start <= end) {
                result.push_back({start, end});
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    for (auto &interval : res) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}
Line Notes
vector<vector<int>> result;Initialize vector to store intersections
for (int i = 0; i < A.size(); i++)Outer loop over intervals in A
for (int j = 0; j < B.size(); j++)Inner loop over intervals in B
int start = max(A[i][0], B[j][0]);Later start time between intervals
int end = min(A[i][1], B[j][1]);Earlier end time between intervals
if (start <= end)Check if intervals overlap
result.push_back({start, end});Add intersection to result
function intervalIntersection(A, B) {
    const result = [];
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B.length; j++) {
            const start = Math.max(A[i][0], B[j][0]);
            const end = Math.min(A[i][1], B[j][1]);
            if (start <= end) {
                result.push([start, end]);
            }
        }
    }
    return result;
}

// Test
const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));
Line Notes
const result = []Initialize array to store intersections
for (let i = 0; i < A.length; i++)Outer loop over intervals in A
for (let j = 0; j < B.length; j++)Inner loop over intervals in B
const start = Math.max(A[i][0], B[j][0])Later start time between intervals
const end = Math.min(A[i][1], B[j][1])Earlier end time between intervals
if (start <= end)Check if intervals overlap
result.push([start, end])Add intersection to result
⏱
Complexity
TimeO(m*n)
SpaceO(m*n)

We compare each interval in A with each interval in B, resulting in m*n comparisons. The result can be up to m*n in worst case.

💡 For 100 intervals in each list, this means 10,000 comparisons, which is inefficient for large inputs.
Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠
Two Pointers Approach
💡 This approach improves efficiency by leveraging the sorted and disjoint nature of the interval lists, using two pointers to traverse both lists simultaneously.

Intuition

Since both lists are sorted and intervals do not overlap within the same list, we can use two pointers to iterate through both lists and find intersections by advancing the pointer with the smaller interval end.

Algorithm

  1. Initialize two pointers i and j at 0 for lists A and B respectively.
  2. While both pointers are within their list bounds, compare intervals A[i] and B[j].
  3. Find the intersection by taking max of starts and min of ends; if they overlap, add to result.
  4. Advance the pointer whose interval ends first to find new potential intersections.
💡 This approach avoids unnecessary comparisons by moving pointers smartly based on interval ends.
</>
Code
from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])
        if start <= end:
            result.append([start, end])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

# Driver code
if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))
Line Notes
i, j = 0, 0Initialize pointers for both lists
while i < len(A) and j < len(B)Loop until one list is exhausted
start = max(A[i][0], B[j][0])Later start time between current intervals
end = min(A[i][1], B[j][1])Earlier end time between current intervals
if start <= endCheck if intervals overlap
result.append([start, end])Add intersection to result
if A[i][1] < B[j][1]Advance pointer with smaller interval end
i += 1Move pointer i forward
elseOtherwise, move pointer j forward
j += 1Move pointer j forward
import java.util.*;

public class IntervalIntersection {
    public static List<int[]> intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int start = Math.max(A[i][0], B[j][0]);
            int end = Math.min(A[i][1], B[j][1]);
            if (start <= end) {
                result.add(new int[]{start, end});
            }
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] A = {{0,2},{5,10},{13,23},{24,25}};
        int[][] B = {{1,5},{8,12},{15,24},{25,26}};
        List<int[]> res = intervalIntersection(A, B);
        for (int[] interval : res) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}
Line Notes
int i = 0, j = 0;Initialize pointers for both lists
while (i < A.length && j < B.length)Loop until one list is exhausted
int start = Math.max(A[i][0], B[j][0]);Later start time between current intervals
int end = Math.min(A[i][1], B[j][1]);Earlier end time between current intervals
if (start <= end)Check if intervals overlap
result.add(new int[]{start, end});Add intersection to result
if (A[i][1] < B[j][1])Advance pointer with smaller interval end
i++;Move pointer i forward
elseOtherwise, move pointer j forward
j++;Move pointer j forward
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> result;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size()) {
        int start = max(A[i][0], B[j][0]);
        int end = min(A[i][1], B[j][1]);
        if (start <= end) {
            result.push_back({start, end});
        }
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    for (auto &interval : res) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}
Line Notes
int i = 0, j = 0;Initialize pointers for both lists
while (i < A.size() && j < B.size())Loop until one list is exhausted
int start = max(A[i][0], B[j][0]);Later start time between current intervals
int end = min(A[i][1], B[j][1]);Earlier end time between current intervals
if (start <= end)Check if intervals overlap
result.push_back({start, end});Add intersection to result
if (A[i][1] < B[j][1])Advance pointer with smaller interval end
i++;Move pointer i forward
elseOtherwise, move pointer j forward
j++;Move pointer j forward
function intervalIntersection(A, B) {
    let i = 0, j = 0;
    const result = [];
    while (i < A.length && j < B.length) {
        const start = Math.max(A[i][0], B[j][0]);
        const end = Math.min(A[i][1], B[j][1]);
        if (start <= end) {
            result.push([start, end]);
        }
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

// Test
const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));
Line Notes
let i = 0, j = 0;Initialize pointers for both lists
while (i < A.length && j < B.length)Loop until one list is exhausted
const start = Math.max(A[i][0], B[j][0])Later start time between current intervals
const end = Math.min(A[i][1], B[j][1])Earlier end time between current intervals
if (start <= end)Check if intervals overlap
result.push([start, end])Add intersection to result
if (A[i][1] < B[j][1])Advance pointer with smaller interval end
i++Move pointer i forward
elseOtherwise, move pointer j forward
j++Move pointer j forward
⏱
Complexity
TimeO(m + n)
SpaceO(m + n)

Each interval is visited at most once by the pointers, resulting in linear time relative to input size.

💡 For 100 intervals in each list, this means about 200 operations, which is efficient for large inputs.
Interview Verdict: Accepted / Optimal for this problem

This approach is efficient and the best practical solution for this problem.

🧠
Two Pointers with Early Skipping
💡 This approach refines the two pointers method by explicitly skipping intervals that cannot overlap, improving clarity and sometimes performance.

Intuition

If one interval ends before the other starts, we can skip it immediately, reducing unnecessary comparisons.

Algorithm

  1. Initialize two pointers i and j at 0.
  2. While both pointers are valid, check if intervals A[i] and B[j] overlap.
  3. If they overlap, add the intersection to the result.
  4. If A[i] ends before B[j] starts, increment i to skip A[i].
  5. Else if B[j] ends before A[i] starts, increment j to skip B[j].
  6. Otherwise, advance the pointer with the smaller end to find new overlaps.
💡 This approach explicitly handles non-overlapping cases first, making the logic clearer and potentially faster.
</>
Code
from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] < B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result

# Driver code
if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))
Line Notes
if A[i][1] < B[j][0]Skip A[i] if it ends before B[j] starts
i += 1Move pointer i forward
elif B[j][1] < A[i][0]Skip B[j] if it ends before A[i] starts
j += 1Move pointer j forward
elseOtherwise, move pointer j forward
start = max(A[i][0], B[j][0])Later start time between intervals
end = min(A[i][1], B[j][1])Earlier end time between intervals
result.append([start, end])Add intersection to result
if A[i][1] < B[j][1]Advance pointer with smaller interval end
import java.util.*;

public class IntervalIntersection {
    public static List<int[]> intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            if (A[i][1] < B[j][0]) {
                i++;
            } else if (B[j][1] < A[i][0]) {
                j++;
            } else {
                int start = Math.max(A[i][0], B[j][0]);
                int end = Math.min(A[i][1], B[j][1]);
                result.add(new int[]{start, end});
                if (A[i][1] < B[j][1]) {
                    i++;
                } else {
                    j++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] A = {{0,2},{5,10},{13,23},{24,25}};
        int[][] B = {{1,5},{8,12},{15,24},{25,26}};
        List<int[]> res = intervalIntersection(A, B);
        for (int[] interval : res) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}
Line Notes
if (A[i][1] < B[j][0])Skip A[i] if it ends before B[j] starts
i++;Move pointer i forward
else if (B[j][1] < A[i][0])Skip B[j] if it ends before A[i] starts
j++;Move pointer j forward
elseOtherwise, move pointer j forward
int start = Math.max(A[i][0], B[j][0]);Later start time between intervals
int end = Math.min(A[i][1], B[j][1]);Earlier end time between intervals
result.add(new int[]{start, end});Add intersection to result
if (A[i][1] < B[j][1])Advance pointer with smaller interval end
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> result;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size()) {
        if (A[i][1] < B[j][0]) {
            i++;
        } else if (B[j][1] < A[i][0]) {
            j++;
        } else {
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            result.push_back({start, end});
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    for (auto &interval : res) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}
Line Notes
if (A[i][1] < B[j][0])Skip A[i] if it ends before B[j] starts
i++;Move pointer i forward
else if (B[j][1] < A[i][0])Skip B[j] if it ends before A[i] starts
j++;Move pointer j forward
elseOtherwise, move pointer j forward
int start = max(A[i][0], B[j][0]);Later start time between intervals
int end = min(A[i][1], B[j][1]);Earlier end time between intervals
result.push_back({start, end});Add intersection to result
if (A[i][1] < B[j][1])Advance pointer with smaller interval end
function intervalIntersection(A, B) {
    let i = 0, j = 0;
    const result = [];
    while (i < A.length && j < B.length) {
        if (A[i][1] < B[j][0]) {
            i++;
        } else if (B[j][1] < A[i][0]) {
            j++;
        } else {
            const start = Math.max(A[i][0], B[j][0]);
            const end = Math.min(A[i][1], B[j][1]);
            result.push([start, end]);
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
    }
    return result;
}

// Test
const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));
Line Notes
if (A[i][1] < B[j][0])Skip A[i] if it ends before B[j] starts
i++Move pointer i forward
else if (B[j][1] < A[i][0])Skip B[j] if it ends before A[i] starts
j++Move pointer j forward
elseOtherwise, move pointer j forward
const start = Math.max(A[i][0], B[j][0])Later start time between intervals
const end = Math.min(A[i][1], B[j][1])Earlier end time between intervals
result.push([start, end])Add intersection to result
if (A[i][1] < B[j][1])Advance pointer with smaller interval end
⏱
Complexity
TimeO(m + n)
SpaceO(m + n)

Each interval is visited at most once, skipping non-overlapping intervals early reduces unnecessary checks.

💡 This approach is as efficient as the previous but can be easier to understand and slightly faster in practice.
Interview Verdict: Accepted / Optimal and clear

This approach is recommended for clarity and performance in interviews.

📊
All Approaches - One-Glance Tradeoffs
💡 The two pointers approach (Approach 2 or 3) is the best choice for interviews due to its efficiency and clarity.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(m*n)O(m*n)NoN/AMention only - never code
2. Two PointersO(m + n)O(m + n)NoN/ACode this approach
3. Two Pointers with Early SkippingO(m + n)O(m + n)NoN/ACode this approach for clarity
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare for common edge cases and follow-ups.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the two pointers approach and why it is efficient.Step 4: Code the two pointers solution carefully.Step 5: Test with examples and edge cases.Step 6: Discuss possible follow-ups or optimizations.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to handle interval comparisons, use two pointers effectively, and write clean, bug-free code.

Common Follow-ups

  • What if intervals are not sorted? → Sort first, then apply two pointers.
  • How to handle open intervals? → Adjust comparison logic accordingly.
  • Can this be extended to k lists? → Use a heap or pairwise intersection.
  • What if intervals overlap within the same list? → Merge intervals first.
💡 These follow-ups test your adaptability and deeper understanding of interval problems.
🔍
Pattern Recognition

When to Use

1) You have two lists of intervals, 2) Both lists are sorted and disjoint internally, 3) You need to find overlapping intervals, 4) Efficient linear time is required.

Signature Phrases

interval list intersectionsfind overlapping intervalstwo sorted lists of intervals

NOT This Pattern When

Problems involving intervals but requiring DP or scheduling optimization are different patterns.

Similar Problems

Merge Intervals - merging overlapping intervals in one listInsert Interval - inserting and merging a new intervalNon-overlapping Intervals - removing overlaps to minimize intervals

Practice

(1/5)
1. You are given a list of intervals and a list of points. For each point, you need to find how many intervals contain it. Which algorithmic approach guarantees an optimal solution with time complexity better than O(n*m), where n is the number of intervals and m is the number of points?
easy
A. Use a line sweep algorithm by sorting interval start and end events along with points, then sweeping through them.
B. Use a brute force nested loop checking each point against every interval.
C. Use dynamic programming to precompute counts for all points in the range.
D. Sort intervals and points, then for each point use binary search to count intervals starting before and ending after the point.

Solution

  1. Step 1: Understand brute force and binary search limitations

    Brute force is O(n*m), too slow for large inputs. Binary search approach requires careful handling of interval ends and starts but is less optimal than line sweep.
  2. Step 2: Recognize line sweep advantages

    Line sweep sorts all events (starts, points, ends) and processes them in one pass, maintaining active intervals count efficiently in O((n+m) log (n+m)) time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Line sweep processes all events sorted by coordinate with correct event ordering [OK]
Hint: Line sweep processes starts, points, ends in sorted order [OK]
Common Mistakes:
  • Assuming binary search alone is optimal
  • Thinking DP applies here
  • Using brute force for large inputs
2. Consider the following code snippet implementing the sweep line algorithm to find the minimum number of platforms required. What is the value of max_platforms returned for the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120]?
easy
A. 4
B. 1
C. 3
D. 2

Solution

  1. Step 1: Create and sort events

    Events: (900,1), (940,1), (950,1), (910,-1), (1200,-1), (1120,-1). Sorted: (900,1), (910,-1), (940,1), (950,1), (1120,-1), (1200,-1).
  2. Step 2: Sweep through events updating platforms_needed and max_platforms

    At 900 arrival: platforms_needed=1, max=1; at 910 departure: platforms_needed=0; at 940 arrival: platforms_needed=1; at 950 arrival: platforms_needed=2, max=2; at 1120 departure: platforms_needed=1; at 1200 departure: platforms_needed=0.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Maximum concurrent trains is 2 [OK]
Hint: Sort events and track increments/decrements [OK]
Common Mistakes:
  • Misordering events when arrival and departure times are close
  • Off-by-one errors in counting platforms
  • Ignoring departure before arrival at same time
3. The following code attempts to implement the optimal car pooling solution. Which line contains a subtle bug that can cause incorrect capacity checks?
def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] += num  # Bug here
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true
medium
A. Line that increments diff[end] by num instead of decrementing
B. Line that updates max_location in the first loop
C. Line that increments diff[start] by num
D. Line that checks if current_passengers exceeds capacity

Solution

  1. Step 1: Understand difference array updates

    Passengers boarding at start location increase count; passengers leaving at end location must decrease count.
  2. Step 2: Identify incorrect update

    Line incrementing diff[end] by num adds passengers instead of removing them, causing incorrect capacity calculation.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Increment at end location breaks capacity tracking [OK]
Hint: End location must decrement passengers, not increment [OK]
Common Mistakes:
  • Incrementing instead of decrementing at end
  • Forgetting to update difference array
  • Checking capacity before summing passengers
4. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?
medium
A. Line 3: Missing check for empty intervals list.
B. Line 9: Incorrect condition using >= instead of > for overlap.
C. Line 11: Using heappush without popping first.
D. Line 6: Intervals are not sorted before processing.

Solution

  1. Step 1: Identify missing sorting.

    Intervals must be sorted by start time before heap processing; missing this breaks heap logic.
  2. Step 2: Confirm other lines.

    Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Without sorting, heap logic fails to track earliest ending meeting [OK]
Hint: Heap logic requires sorted intervals by start time [OK]
Common Mistakes:
  • Confusing overlap condition with <=
  • Forgetting to sort intervals
  • Misordering heap push/pop
5. The following code attempts to find the maximum number of non-overlapping intervals. Which line contains a subtle bug that can cause incorrect results on some inputs?
def max_non_overlapping_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    removals = 0
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= last_end:
            removals += 1
            last_end = min(last_end, intervals[i][1])
        else:
            last_end = intervals[i][1]
    return len(intervals) - removals
medium
A. Line 9: Updating last_end to intervals[i][1] when no overlap
B. Line 2: Sorting intervals by start time instead of end time
C. Line 7: Updating last_end to min(last_end, intervals[i][1]) inside overlap condition
D. Line 5: Using '<=' instead of '<' in the overlap condition

Solution

  1. Step 1: Understand overlap condition

    Intervals that start exactly at last_end do not overlap and should be allowed.
  2. Step 2: Identify incorrect operator

    Using '<=' causes intervals starting exactly at last_end to be considered overlapping, reducing count incorrectly.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Change '<=' to '<' fixes the bug [OK]
Hint: Overlap check must use strict less than, not less or equal [OK]
Common Mistakes:
  • Confusing inclusive vs exclusive overlap conditions
  • Sorting by start time is allowed but less optimal
  • Incorrect last_end updates
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard