Set Intersection Size At Least Two


  • 0

    Click here to see the full article post


  • 0
    T

    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);
            
        }
    }
    

  • 1
    S

    @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


  • 0
    E

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

     int e = intervals[t][1];
    

  • 0
    T

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


  • 0
    L

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


  • 0
    M

    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?


  • 0
    M

    Edit: O(n log n) time.


Log in to reply
 

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