【leetcode】757. Set Intersection Size At Least Two

题目如下：

解题思路：贪心算法。首先把intervals按第二个元素从小到大排序，然后遍历intervals,如果集合S和intervals[i]没有交集，那么把intervals[i]的最大值和次大值加入集合S；如果交集只有一个元素，则把最大值加入S。

代码如下：

class Solution(object):

    def intersectionSizeTwo(self, intervals):

        """

        :type intervals: List[List[int]]

        :rtype: int

        """

        import bisect

        def cmpf(l1,l2):

            if l1[1] != l2[1]:

                return l1[1] - l2[1]

            return l2[0] - l1[0]

        intervals.sort(cmp=cmpf)

        res = None

        for low,high in intervals:

            if low == 29 and high == 37:

                pass

            if res == None:

                res = [high-1,high]

            elif res[-1] < low:

                #res[1] = low + 1

                res.append(high-1)

                res.append(high)

            elif res[-1] == low:

                res.append(high)

            elif bisect.bisect_right(res,high) -  bisect.bisect_left(res,low)  == 1:

                res.append(high)

            #print res

        #print intervals

        #print res

        return len(res)

巴特西

【leetcode】757. Set Intersection Size At Least Two

最新文章

热门文章