Leetcode 757. Set Intersection Size At Least Two
Problem Explanation
The goal of this problem is to find the minimum size of a set S. This set has the property that for every interval A that exists in the intervals we have as input, the intersection of S with A should have at least 2 elements.
Example Walkthrough
For instance, let's take the example of intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]. The set S could be {2, 3, 4}. It is easy to see that for each interval, there are at least 2 elements from S in the interval:
- [1, 3] intersect S gives {2, 3}
- [1, 4] intersect S gives {2, 3, 4}
- [2, 5] intersect S gives {2, 3, 4}
- [3, 5] intersect S gives {3, 4} And it's also easy to see that we can't obtain a smaller set than this, that satisfies the condition for all intervals.
Let's notice that S should contain numbers that appear in more intervals, to reduce its size. This is actually the core idea of the approach to solve this problem.
Solution Approach
To solve this problem, we first sort the intervals by their right end, and if two intervals have the same right end we sort them by their left end in descending order. This way the interval with the larger left end will come first and we have more chance to satisfy later intervals without adding more elements to the set S.
Java
1 2java 3class Solution { 4 public int intersectionSizeTwo(int[][] intervals) { 5 // Sorting the intervals based on two criteria. 6 Arrays.sort(intervals, (a, b) -> { 7 if (a[1] == b[1]) { 8 return b[0] - a[0]; 9 } else { 10 return a[1] - b[1]; 11 } 12 }); 13 14 // Initializing variables. 15 int count = 2; 16 int lastOne = intervals[0][1]; 17 int secondLastOne = lastOne - 1; 18 19 // Iterating through the rest of intervals. 20 for (int i = 1; i < intervals.length; i++) { 21 // If the current interval is covered by the last two elements, we don't need to add anything to the set. 22 if (secondLastOne >= intervals[i][0]) { 23 continue; 24 } 25 // If the current interval is covered by the last one element, we only need to add one element to the set. 26 else if (lastOne >= intervals[i][0]) { 27 secondLastOne = lastOne; 28 lastOne = intervals[i][1]; 29 count++; 30 } 31 // Otherwise, we need to add two elements to the set. 32 else { 33 secondLastOne = intervals[i][1] - 1; 34 lastOne = intervals[i][1]; 35 count += 2; 36 } 37 } 38 39 // Returning the size of the set. 40 return count; 41 } 42}
Python
1 2python 3class Solution: 4 def intersectionSizeTwo(self, intervals: List[List[int]]) -> int: 5 # Sorting the intervals based on two criteria. 6 intervals.sort(key=lambda x: (x[1], -x[0])) 7 8 # Initializing variables. 9 count = 2 10 lastOne = intervals[0][1] 11 secondLastOne = lastOne - 1 12 13 # Iterating through the rest of intervals. 14 for i in range(1, len(intervals)): 15 # If the current interval is covered by the last two elements, we don't need to add anything to the set. 16 if secondLastOne >= intervals[i][0]: 17 continue 18 # If the current interval is covered by the last one element, we only need to add one element to the set. 19 elif lastOne >= intervals[i][0]: 20 secondLastOne = lastOne 21 lastOne = intervals[i][1] 22 count += 1 23 # Otherwise, we need to add two elements to the set. 24 else: 25 secondLastOne = intervals[i][1] - 1 26 lastOne = intervals[i][1] 27 count += 2 28 29 # Returning the size of the set. 30 return count
C#
1 2csharp 3public class Solution { 4 public int IntersectionSizeTwo(int[][] intervals) { 5 // Sorting the intervals based on two criteria. 6 Array.Sort(intervals, (a, b) => a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]); 7 8 // Initializing variables. 9 int count = 2; 10 int lastOne = intervals[0][1]; 11 int secondLastOne = lastOne - 1; 12 13 // Iterating through the rest of intervals. 14 for (int i = 1; i < intervals.Length; i++) { 15 // If the current interval is covered by the last two elements, we don't need to add anything to the set. 16 if (secondLastOne >= intervals[i][0]) { 17 continue; 18 } 19 // If the current interval is covered by the last one element, we only need to add one element to the set. 20 else if (lastOne >= intervals[i][0]) { 21 secondLastOne = lastOne; 22 lastOne = intervals[i][1]; 23 count++; 24 } 25 // Otherwise, we need to add two elements to the set. 26 else { 27 secondLastOne = intervals[i][1] - 1; 28 lastOne = intervals[i][1]; 29 count += 2; 30 } 31 } 32 33 // Returning the size of the set. 34 return count; 35 } 36}
C++
1 2cpp 3class Solution { 4public: 5 int intersectionSizeTwo(vector<vector<int>>& intervals) { 6 // Sorting the intervals based on two criteria. 7 sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) { 8 return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]); 9 }); 10 11 // Initializing variables. 12 int count = 2; 13 int lastOne = intervals[0][1]; 14 int secondLastOne = lastOne - 1; 15 16 // Iterating through the rest of intervals. 17 for (int i = 1; i < intervals.size(); i++) { 18 // If the current interval is covered by the last two elements, we don't need to add anything to the set. 19 if (secondLastOne >= intervals[i][0]) { 20 continue; 21 } 22 // If the current interval is covered by the last one element, we only need to add one element to the set. 23 else if (lastOne >= intervals[i][0]) { 24 secondLastOne = lastOne; 25 lastOne = intervals[i][1]; 26 count++; 27 } 28 // Otherwise, we need to add two elements to the set. 29 else { 30 secondLastOne = intervals[i][1] - 1; 31 lastOne = intervals[i][1]; 32 count += 2; 33 } 34 } 35 36 // Returning the size of the set. 37 return count; 38 } 39};
Javascript
1 2javascript 3var intersectionSizeTwo = function(intervals) { 4 // Sorting the intervals based on two criteria. 5 intervals.sort(function(a, b) { 6 return a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]; 7 }); 8 9 // Initializing variables. 10 let count = 2; 11 let secondLastOne = intervals[0][1] - 1; 12 let lastOne = intervals[0][1]; 13 14 // Iterating through the rest of intervals. 15 for (let i = 1; i < intervals.length; i++) { 16 // If the current interval is covered by the last two elements, we don't need to add anything to the set. 17 if (secondLastOne >= intervals[i][0]) { 18 continue; 19 } 20 // If the current interval is covered by the last one element, we only need to add one element to the set. 21 else if (lastOne >= intervals[i][0]) { 22 secondLastOne = lastOne; 23 lastOne = intervals[i][1]; 24 count++; 25 } 26 // Otherwise, we need to add two elements to the set. 27 else { 28 secondLastOne = intervals[i][1] - 1; 29 lastOne = intervals[i][1]; 30 count += 2; 31 } 32 } 33 34 // Returning the size of the set. 35 return count; 36};
Time and Space Complexity
The time complexity of the above problem is O(n log n) where n is the size of the intervals list due to sorting the list. The space complexity is O(1) as we are using a constant amount of space to store our result and temporary variables.## Rust
Rust is a systems programming language that runs extremely fast, prevents crashes, and denies null. This memory-safe language has syntax supporting advanced type checking to avoid as many programming errors as possible during compilation.
Let's define a solution using Rust:
1 2rust 3struct Solution; 4 5impl Solution { 6 pub fn intersection_size_two(intervals: Vec<Vec<i32>>) -> i32 { 7 let mut intervals = intervals; 8 9 // Sorting the intervals based on two criteria. 10 intervals.sort_by(|a, b| a[1].cmp(&b[1]).then_with(|| b[0].cmp(&a[0]))); 11 12 // Initializing variables. 13 let mut count = 2; 14 let mut lastOne = intervals[0][1]; 15 let mut secondLastOne = lastOne - 1; 16 17 // Iterating through the rest of intervals. 18 for i in 1..intervals.len() { 19 // If the current interval is covered by the last two elements, we don't need to add anything to the set. 20 if secondLastOne >= intervals[i][0] { 21 continue; 22 } 23 // If the current interval is covered by the last one element, we only need to add one element to the set. 24 else if lastOne >= intervals[i][0] { 25 secondLastOne = lastOne; 26 lastOne = intervals[i][1]; 27 count += 1; 28 } 29 // Otherwise, we need to add two elements to the set. 30 else { 31 secondLastOne = intervals[i][1] - 1; 32 lastOne = intervals[i][1]; 33 count += 2; 34 } 35 } 36 37 // Returning the size of the set. 38 count 39 } 40}
Kotlin
Kotlin is a programming language developed by Google for modern multi-platform applications. It's great for android developers as it simplifies common programming task and make code easy to read.
Here is solution in Kotlin:
1 2kotlin 3class Solution { 4 fun intersectionSizeTwo(intervals: Array<IntArray>): Int { 5 // Sorting the intervals based on two criteria. 6 intervals.sortWith(Comparator { a: IntArray, b: IntArray -> if (a[1] == b[1]) b[0] - a[0] else a[1] - b[1] }) 7 8 // Initializing variables. 9 var count = 2 10 var lastOne = intervals[0][1] 11 var secondLastOne = lastOne - 1 12 13 // Iterating through the rest of intervals. 14 for (i in 1 until intervals.size) { 15 // If the current interval is covered by the last two elements, we don't need to add anything to the set. 16 if (secondLastOne >= intervals[i][0]) { 17 continue 18 } 19 // If the current interval is covered by the last one element, we only need to add one element to the set. 20 else if (lastOne >= intervals[i][0]) { 21 secondLastOne = lastOne 22 lastOne = intervals[i][1] 23 count++ 24 } 25 // Otherwise, we need to add two elements to the set. 26 else { 27 secondLastOne = intervals[i][1] - 1 28 lastOne = intervals[i][1] 29 count += 2 30 } 31 } 32 33 // Returning the size of the set. 34 return count 35 } 36}
Conclusion
To solve the problem, we first sort the intervals by their right end. After sorting, we iterate over the intervals and check if they're already covered by the elements in the set. If the interval is covered, we continue to the next interval. If the interval is not fully covered, we add the necessary number of elements to the set. The final solution provided here is efficient, clean and works in different languages.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.