# Set Intersection Size At Least Two

• I have submitted my solution and it passed 19 tests but did not pass one with intervals spread from 2,10 to 11,12. Sorry did not copy the example.
I have checked manually a few times, and I think that my solution (below) is correct, and test result is incorrect.

To my understanding the set of numbers in resulting set has to be 6-12 which brings the result 7 instead of 5 as shown in the test result.
My solution is somewhat similar to above, but less elegant :).

``````class Solution {
public int intersectionSizeTwo(int[][] intervals) {
//first find an interval, then minimize it
//look for min beginning, max ending
int maxB = -1; // no negatives in setup
int minA = 100000001;
int[] count = new int[intervals.length];
int maxA = -1;
int minB = minA;
for (int i = 0; i < intervals.length;i++){
//smallest beginning
if (intervals[i][0] < minA){
minA = intervals[i][0];
}
//biggest ending
if (intervals[i][1] > maxB){
maxB= intervals[i][1];
}
//biggest beginning
if (intervals[i][0] > maxA){
maxA = intervals[i][0];
}
//smallest ending
if (intervals[i][1] < minB){
minB= intervals[i][1];
}
}
//now interval minA,maxB includes all numbers; overkill maybe
//look what we can cut

for (int i = 0; i < intervals.length;i++){
//look at the smallest interval intersection
if (intervals[i][1] - maxA >= 1) {
//there is an intersection
//maxA is OK
} else {

maxA =  intervals[i][1] - 1;
}
//look at the smallest interval intersection
if (minB - intervals[i][0]>= 1) {
//there is an intersection
//minB is OK
} else {

minB = intervals[i][0] + 1;
}
}
return (minB - maxA + 1);

}
}
``````

• @tmerzlyak: I think the test case that made you fail is
[[2,10],[3,7],[3,15],[4,11],[6,12],[6,16],[7,8],[7,11],[7,15],[11,12]]
But the result is 5 indeed, say if you choose 6, 7, 8, 11, 12, you can see each interval contains at least 2 numbers

• Nice solution! Below LOC could be removed, we are not using e.

`````` int e = intervals[t][1];
``````

• @szp_14163.com Thanks. Now I see that I misunderstood the problem. I thought the solution should be another interval that intersect each by min 2 numbers. But if it is just a set of numbers it makes sense now.

• I found @uwi 's answer can not pass [[1,10],[10,24],[23,24],[24,35]]

• I think I can solve it in `O(n)` time for open intervals `[a, b)` as follows:

``````from operator import itemgetter

class Solution:
def intersectionSizeTwo(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
if len(intervals) < 1:
return 0

# Sort by finish time
intervals = sorted(intervals, key=itemgetter(1))

# Get finish time from first element
f = intervals[0][1]

A = set([f - 1, f])

# Temporary set
B = set()

k = 0

for i in range(1, len(intervals)):
s = intervals[i][0]
f = intervals[i][1]

if s > intervals[k][1]:
A |= {f - 1, f}
k = i
elif s >= intervals[k][1]:
A |= {f}
k = i

return len(A)
``````

Any idea on how I can extend this to closed intervals?

• Edit: `O(n log n)` time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.