题目如下:

【leetcode】757. Set Intersection Size At Least Two-LMLPHP

解题思路:贪心算法。首先把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)
05-28 02:22