Set Intersection Size At Least Two

Hard
1441.

Set Intersection Size At Least Two

Set Intersection Size At Least Two is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

Each intervals[i] = [start, end] stands for every integer from start to end, both included.

A set of integers nums is containing if every interval holds at least two of its integers.

Return the smallest possible size of a containing set.

Example 1

Input
intervals = [[1,3],[3,7],[8,9]]
Output
5
Explanation
For example {2, 3, 4, 8, 9}: [1,3] holds 2 and 3, [3,7] holds 3 and 4, [8,9] holds 8 and 9.

Example 2

Input
intervals = [[1,3],[1,4],[2,5],[3,5]]
Output
3
Explanation
{2, 3, 4} works.

Example 3

Input
intervals = [[1,2],[2,3],[2,4],[4,5]]
Output
5

Constraints

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= start < end <= 10^8
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var intersectionSizeTwo = function(intervals) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Set Intersection Size At Least Two — Problem & Solution

Set Intersection Size At Least Two solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Set Intersection Size At Least Two is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each intervals[i] = [start, end] stands for every integer from start to end, both included.

A set of integers nums is containing if every interval holds at least two of its integers.

Return the smallest possible size of a containing set.

Example 1

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: For example {2, 3, 4, 8, 9}: [1,3] holds 2 and 3, [3,7] holds 3 and 4, [8,9] holds 8 and 9.

Example 2

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: {2, 3, 4} works.

Example 3

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

Constraints

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= start < end <= 10^8

Hints for Set Intersection Size At Least Two

  1. Hint 1

    Process intervals by increasing end. When an interval still needs points, the best points to add are the largest ones it contains — they reach furthest into later intervals.

  2. Hint 2

    You only need to remember the two largest points chosen so far.

  3. Hint 3

    Sort by end ascending and, for equal ends, by start descending. Then each interval needs 0, 1 (add end) or 2 (add end - 1 and end) new points depending on how many of the two largest chosen points it already contains.

How to solve Set Intersection Size At Least Two

A greedy that always picks points as far right as possible. Among intervals sorted by right end, the current one must get its missing points somewhere inside it, and choosing them at its right end keeps the most options open for the intervals that end later.

Approach

  1. Sort intervals by end ascending; break ties by start descending (narrower first).
  2. Keep a < b, the two largest points chosen so far (initially below every coordinate), and count = 0.
  3. For each [s, e]: if s <= a, both are inside — nothing to do. Else if s <= b, only b is inside: add e, so a = b, b = e, count += 1. Otherwise add e - 1 and e: a = e - 1, b = e, count += 2.
  4. Return count.

Why it works

Every chosen point is at most the current interval's end, because earlier intervals end no later. So the chosen points inside [s, e] are exactly those >= s, and only the two largest matter: if the second largest a is >= s, the interval already holds two. When points must be added, any point in [s, e] works for this interval, and a larger one is in every later interval that a smaller one is in (later intervals end at or after e), so e and e - 1 dominate. The tie order guarantees that when s <= b < ... the new point e differs from b.

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • Without the start-descending tie break, two intervals with the same end can make the greedy add e twice.
  • The two tracked points must be the two largest chosen, updated as a sliding pair.
  • Intervals are inclusive, so [3,7] contains 3: the shared point can serve both [1,3] and [3,7].

Reference solution

Python

from typing import List

def intersectionSizeTwo(intervals: List[List[int]]) -> int:
    ivs = sorted(intervals, key=lambda iv: (iv[1], -iv[0]))
    a, b = -1, -1  # the two largest chosen points, a < b
    count = 0
    for s, e in ivs:
        if s <= a:
            continue
        if s <= b:
            count += 1
            a, b = b, e
        else:
            count += 2
            a, b = e - 1, e
    return count

Java

public static int intersectionSizeTwo(int[][] intervals) {
    int[][] ivs = intervals.clone();
    Arrays.sort(ivs, (x, y) -> x[1] != y[1] ? Integer.compare(x[1], y[1]) : Integer.compare(y[0], x[0]));
    int a = -1, b = -1; // the two largest chosen points, a < b
    int count = 0;
    for (int[] iv : ivs) {
        int s = iv[0], e = iv[1];
        if (s <= a) continue;
        if (s <= b) {
            count += 1;
            a = b;
            b = e;
        } else {
            count += 2;
            a = e - 1;
            b = e;
        }
    }
    return count;
}

C++

int intersectionSizeTwo(vector<vector<int>>& intervals) {
    vector<vector<int>> ivs = intervals;
    sort(ivs.begin(), ivs.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[1] != y[1] ? x[1] < y[1] : x[0] > y[0];
    });
    int a = -1, b = -1; // the two largest chosen points, a < b
    int count = 0;
    for (auto& iv : ivs) {
        int s = iv[0], e = iv[1];
        if (s <= a) continue;
        if (s <= b) {
            count += 1;
            a = b;
            b = e;
        } else {
            count += 2;
            a = e - 1;
            b = e;
        }
    }
    return count;
}

JavaScript

var intersectionSizeTwo = function(intervals) {
    var ivs = intervals.slice().sort(function(x, y) { return x[1] - y[1] || y[0] - x[0]; });
    var a = -1, b = -1; // the two largest chosen points, a < b
    var count = 0;
    for (var i = 0; i < ivs.length; i++) {
        var s = ivs[i][0], e = ivs[i][1];
        if (s <= a) continue;
        if (s <= b) {
            count += 1;
            a = b;
            b = e;
        } else {
            count += 2;
            a = e - 1;
            b = e;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms