HardNo. 0757
Set Intersection Size At Least Two — LeetCode 757 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively. A containing set is an array nums where each interval from intervals has at least two integers in nums.
Example
- Input
- intervals = [[1,3],[3,7],[8,9]]
- Output
- 5
- Explanation
- let nums = [2, 3, 4, 8, 9].
Python solution
class Solution:
def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[1], -x[0]))
s = e = -1
ans = 0
for a, b in intervals:
if a <= s:
continue
if a > e:
ans += 2
s, e = b - 1, b
else:
ans += 1
s, e = e, b
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(log n)where n is the number of intervals
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 757. Set Intersection Size At Least Two is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0179 | Largest Number | Medium |
| 0324 | Wiggle Sort II | Medium |
| 0452 | Minimum Number of Arrows to Burst Balloons | Medium |
| 0455 | Assign Cookies | Easy |
| 0502 | IPO | Hard |
| 0561 | Array Partition | Easy |
Frequently asked questions
- How hard is LeetCode 757. Set Intersection Size At Least Two?
LeetCode 757. Set Intersection Size At Least Two is rated Hard on LeetCode.
- What is the time complexity of LeetCode 757. Set Intersection Size At Least Two?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 757. Set Intersection Size At Least Two?
The Python solution on this page uses O(log n), where n is the number of intervals auxiliary space.
- What topics does LeetCode 757. Set Intersection Size At Least Two cover?
LeetCode 757. Set Intersection Size At Least Two is tagged Greedy, Array and Sorting on LeetCode.