757. Set Intersection Size At Least Two
Approach
Greedy. Sort intervals by end ascending (ties broken by start descending).
Track the last two selected intersection points. For each interval, add 0, 1, or 2
new points (the last two of that interval) based on how many tracked points it covers.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Greedy. Sort intervals by end ascending (ties broken by start descending).
// Track the last two selected intersection points. For each interval, add 0, 1, or 2
// new points (the last two of that interval) based on how many tracked points it covers.
// Time: O(n log n) Space: O(1)
public class Solution
{
public int IntersectionSizeTwo(int[][] intervals)
{
// Sort intervals by end point ascending, if equal then by start point descending
// This ensures we process intervals with earlier endpoints first
// When endpoints are equal, we prefer intervals with larger start points (smaller intervals)
Array.Sort(intervals, (a, b) => a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
// Initialize the result counter for minimum points needed
int result = 0;
// Track the last two points in our intersection set
// secondLast: the second-to-last point added to the set
// last: the most recent point added to the set
int secondLast = -1;
int last = -1;
// Process each interval in sorted order
foreach (var interval in intervals)
{
int start = interval[0];
int end = interval[1];
// Case 1: Current interval already contains both tracked points
// No new points needed
if (start <= secondLast)
continue;
// Case 2: Current interval doesn't contain any of the tracked points
// Need to add 2 new points (the last two points of current interval)
if (start > last)
{
result += 2;
secondLast = end - 1;
last = end;
}
// Case 3: Current interval contains only the last point
// Need to add 1 new point (the endpoint of current interval)
else
{
result += 1;
secondLast = last;
last = end;
}
}
return result;
}
}