759. Set Intersection Size At Least Two¶

Difficulty: Hard

759. Set Intersection Size At Least Two

Hard

You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

Example 1:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.

Example 2:

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.

Example 3:

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.

Constraints:

1 <= intervals.length <= 3000
intervals[i].length == 2
0 <= start_i < end_i <= 10⁸

Solution¶

class Solution {
    static class Pair {
        int start, end;
        public Pair(int start, int end) {
            this.start = start;
            this.end = end;
        }
        @Override
        public String toString() {
            return "(" + start + " " + end + ")";
        }
    }
    static class custom_sort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            int op1 = Integer.compare(first.end, second.end);
            if (op1 != 0) return op1;
            return Integer.compare(second.start, first.start);
        }
    }
    public int intersectionSizeTwo(int[][] intervals) {
        int n = intervals.length;
        ArrayList<Pair> res = new ArrayList<>();
        for (int current[] : intervals) {
            int start = current[0], end = current[1];
            res.add(new Pair(start, end));
        }   
        Collections.sort(res, new custom_sort());
        int last = res.get(0).end, slast = res.get(0).end - 1, set_size = 2;
        for (int i = 1; i < n; i++) {
            int current_start = res.get(i).start;
            int current_end = res.get(i).end;
            if (last >= current_start && slast >= current_start) continue;
            if (last >= current_start) {
                slast = last;
                last = current_end;
                set_size++;
            }
            else {
                last = current_end;
                slast = current_end - 1;
                set_size += 2;
            }
        }
        return set_size;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here