Set Intersection Size At Least Two - Practice Coding Problems

Set Intersection Size At Least Two - Problem

You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

Input & Output

Example 1 — Basic Case

$ Input: intervals = [[1,3], [3,7], [8,9]]

› Output: 5

💡 Note: We need a set where each interval has at least 2 numbers. One optimal set is [2,3,7,8,9]: interval [1,3] contains {2,3}, interval [3,7] contains {3,7}, interval [8,9] contains {8,9}.

Example 2 — Overlapping Intervals

$ Input: intervals = [[1,3], [1,4], [2,5], [3,5]]

› Output: 3

💡 Note: One optimal set is [2,3,4]: all intervals contain at least 2 of these numbers.

Example 3 — Single Interval

$ Input: intervals = [[1,2]]

› Output: 2

💡 Note: The interval [1,2] needs at least 2 numbers, so minimum set is [1,2].

Constraints

1 ≤ intervals.length ≤ 3000
intervals[i].length == 2
0 ≤ start_i < end_i ≤ 3000

Visualization

Tap to expand

Understanding the Visualization

Input

Intervals that each need ≥2 numbers

Process

Find optimal set covering all intervals

Output

Minimum size of containing set

Key Takeaway

🎯 Key Insight: Sort by end points and greedily select rightmost numbers to maximize future coverage

Asked in

G Google 25 f Facebook 18 M Microsoft 15

The key insight is to use a greedy approach: sort intervals by end points and select the rightmost possible numbers to maximize coverage for future intervals. Best approach is greedy sorting with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Sort by End Points	O(n log n)	O(1)	Sort intervals by end points and greedily select rightmost valid numbers
Brute Force - Generate All Sets	O(2^n × m)	O(n)	Generate all possible containing sets and find the minimum size

Greedy - Sort by End Points — Algorithm Steps

Sort intervals by end points
For each interval, check how many numbers from current set are already in it
If less than 2, add rightmost numbers from the interval to reach 2
Continue until all intervals are covered

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort intervals by end points

Select

Greedily choose rightmost numbers

Track

Keep track of last two selected numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* ia = (int*)a;
    int* ib = (int*)b;
    return ia[1] - ib[1];
}

int solution(int intervals[][2], int intervalCount) {
    if (intervalCount == 0) return 0;
    
    // Sort intervals by end point
    qsort(intervals, intervalCount, sizeof(int[2]), compare);
    
    // Track the last two numbers added to the set
    int p1 = -1, p2 = -1;
    int count = 0;
    
    for (int i = 0; i < intervalCount; i++) {
        int start = intervals[i][0], end = intervals[i][1];
        
        if (p1 < start) {
            // Neither p1 nor p2 are in current interval
            p1 = end - 1;
            p2 = end;
            count += 2;
        } else if (p2 < start) {
            // Only p1 is in current interval
            p1 = p2;
            p2 = end;
            count += 1;
        }
        // If both p1 and p2 are in interval, continue
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small cases
    int intervals[100][2];
    int count = 0;
    
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            sscanf(ptr, "[%d,%d]", &intervals[count][0], &intervals[count][1]);
            count++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(intervals, count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting intervals takes O(n log n), processing each interval takes O(1)

⚡ Linearithmic

Space Complexity

O(1)

Only need to track last two selected numbers, no additional data structures

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Sort by End Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler