Set Intersection Size At Least Two

LWC 65: 757. Set Intersection Size At Least Two

Problem:

An integer interval [a, b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b. Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has size at least 2.

Example 1:

Input: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]] Output: 3 Explanation: Consider the set S = {2, 3, 4}. For each interval, there are at least 2 elements from S in the interval. Also, there isn’t a smaller size set that fulfills the above condition. Thus, we output the size of this set, which is 3.

Example 2:

Input: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]] Output: 5 Explanation: An example of a minimum sized set is {1, 2, 3, 4, 5}.

Note:

  • intervals will have length in range [1, 3000].
  • intervals[i] will have length 2, representing some integer interval.
  • intervals[i][j] will be an integer in [0, 10^8].

思路: 在选择区间中的元素时,我们可以随意选, 但随意选的后果是不能让set最优,所以可以从侧面反映出如果有【规则】的选择,可能达到全局最优。一个思路:对end进行排序,这样我们就能根据end进行规则的选择了。 1. 很明显,对于待选区间,如果之前没有元素被选择过,那么一定选择最后两个元素,这样能够覆盖的后续区间最多,不过此时需要判断一下,选择两个元素之后,后续区间是否都包含该两个元素。包含一个+1, 包含两个+2,不包含则跳出。 2. 对于一个元素被选择了,我们依旧选取当前区间的最后一个元素,不过此时只选择了一个,所以只需要测试后续区间是否包含该元素即可。

Java版本:

    class P implements Comparable<P>{
        int s;
        int e;
        int c;

        P(int s, int e){
            this.s = s;
            this.e = e;
            this.c = 0;
        }

        @Override
        public int compareTo(P o) {
            return this.e - o.e;
        }
    }

    public int intersectionSizeTwo(int[][] intervals) {
        List<P> ps = new ArrayList<>();
        int n = intervals.length;
        for (int i = 0; i < n; ++i) {
            ps.add(new P(intervals[i][0], intervals[i][1]));
        }
        Collections.sort(ps);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            P inter = ps.get(i);
            if (inter.c == 0) {
                int pos = i + 1;
                while (pos < n && ps.get(pos).s <= inter.e) {
                    ps.get(pos).c ++;
                    if (ps.get(pos).s < inter.e) {
                        ps.get(pos).c ++;
                    }
                    pos ++;
                }
                ans += 2;
            }
            else if (inter.c == 1){
                int pos = i + 1;
                while (pos < n && ps.get(pos).s <= inter.e) {
                    ps.get(pos).c ++;
                    pos ++;
                }
                ans ++;
            }
        }
        return ans;
    }

Python版本:

    def intersectionSizeTwo(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        intervals.sort(key = lambda x : x[1])
        n = len(intervals)
        cnt = [0] * n

        ans = 0
        for i in range(n):
            interval = intervals[i]
            if cnt[i] == 0:
                pos = i + 1
                while pos < n and intervals[pos][0] <= interval[1]:
                    cnt[pos] += 1
                    if (intervals[pos][0] < interval[1]):
                        cnt[pos] += 1
                    pos += 1
                ans += 2
            elif cnt[i] == 1:
                pos = i + 1
                while pos < n and intervals[pos][0] <= interval[1]:
                    cnt[pos] += 1
                    pos += 1
                ans += 1
        return ans

该问题的切入点:明确每个区间都需要选择两个元素,这样就能找到选取元素的可能准则了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券