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 612 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

@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 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?