[已解决]Python：每日一题 371

zltzlt

今天的题目：

一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数（包括 a 和 b）。

给定一组整数区间 intervals，找出一个最小的集合 S，使得 S 里的元素与区间 intervals 中的每一个整数区间都至少有 2 个元素相交。

返回这个最小集合 S 的大小。

说明：S 不一定是连续整数。

示例 1：

输入：intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出：3
解释：最小的集合是 {2, 3, 4}。

示例 2：

输入：intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出：5
解释：最小的集合是 {1, 2, 3, 4, 5}。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

whosyourdaddy

2020-4-8 23:14:10

1. def func371(intervals):
   
2.     count = 0
   
3.     newlist = sorted(intervals,key = lambda s:s[1])
   
4.     result = [(newlist[0][1]-1),newlist[0][1]]
   
5.     for i in range(1,len(newlist)):
   
6.         for j in result:
   
7.             if j <=newlist[i][1] and j>=newlist[i][0]:
   
8.                 count += 1
   
9.                 temp = j
   
10.             if count == 2:
    
11.                 break
    
12.         if count == 0:
    
13.             result.append((newlist[i][1]-1))
    
14.             result.append(newlist[i][1])
    
15.         if count == 1:
    
16.             if temp !=newlist[i][1]:
    
17.                 result.append(newlist[i][1])
    
18.             else:
    
19.                 result.append(newlist[i][1]-1)
    
20.         count = 0
    
21.     return len(result)

复制代码

跳转到最佳答案楼层

风魔孤行者

1. def f(i):
   
2.     min1 = i[0][0]
   
3.     max1 = i[0][1]
   
4.     for each in i:
   
5.         if each[0]>min1:
   
6.             min1 = each[0]
   
7.         if each[1]<max1:
   
8.             max1 = each[1]
   
9.     if max1-min1>=1:
   
10.         return 2
    
11.     else:
    
12.         return min1-max1+3

复制代码

TJBEST

不知道写的对不对，没有严格的证明。试了几个例子是对的

1. def fun371(intervals):
   
2.     def inner(eachSeg):
   
3.         result = 0
   
4.         index = 0
   
5.         M = len(eachSeg)
   
6.         Tail = 0
   
7.         while index < M - 1:
   
8.             state = False
   
9.             for innerindex in range(index+1,M):
   
10.                 if eachSeg[index][1] > eachSeg[innerindex][0]:
    
11.                     state = True
    
12.                 else:
    
13.                     break
    
14.             else:
    
15.                 innerindex += 1
    
16.             if state == True:
    
17.                 result += 2
    
18.             else:
    
19.                 result += 2 - Tail
    
20.             if innerindex == M:
    
21.                 break
    
22.             else:
    
23.                 if eachSeg[index][1] == eachSeg[innerindex][0]:
    
24.                     Tail = 1
    
25.                 else:
    
26.                     Tail = 0
    
27.                 index = innerindex
    
28.         else:
    
29.             result += 2 - Tail
    
30.         return result           
    
31.     sortedArr = sorted(intervals)
    
32. #第一次保留子集
    
33.     M = len(sortedArr)
    
34.     for index in range(M-1,0,-1):
    
35.         if sortedArr[index][0] == sortedArr[index-1][0]:
    
36.             del sortedArr[index]
    
37. #第二次保留子集，并分组
    
38.     Seg = []
    
39.     temp = []
    
40.     for each in sortedArr:
    
41.         if temp != []:
    
42.             N = len(temp)
    
43.             for index in range(N-1,-1,-1):
    
44.                 if each[1] <= temp[index][1]:
    
45.                     del temp[index]
    
46.                 else:
    
47.                     break
    
48.             if temp == [] or each[0] <= temp[-1][1]:
    
49.                temp.append(each)
    
50.             else:
    
51.                 Seg.append(temp)
    
52.                 temp = [each]
    
53.         else:
    
54.            temp.append(each)
    
55.     else:
    
56.         Seg.append(temp)
    
57. #计算每一个分组的值进行叠加
    
58.     result = 0
    
59.     for each in Seg:
    
60.         result += inner(each)
    
61.     return result

复制代码

kinkon

例1的区间是1-5吗？返回1-3好像是最小的啊？

ouyunfu

1. def f371(intervals:list)->int:
   
2.     l=len(intervals)
   
3.     m,n=max([intervals[i][0] for i in range(l)]),min([intervals[i][1] for i in range(l)])
   
4.     return 2 if n-m>=1 else m-n+3

复制代码

TJBEST

@zltzlt intervals 是否排好序了？

永恒的蓝色梦想

前排

zltzlt

TJBEST 发表于 2020-4-8 21:23
@zltzlt intervals 是否排好序了？

不一定

whosyourdaddy

1. def func371(intervals):
   
2.     count = 0
   
3.     newlist = sorted(intervals,key = lambda s:s[1])
   
4.     result = [(newlist[0][1]-1),newlist[0][1]]
   
5.     for i in range(1,len(newlist)):
   
6.         for j in result:
   
7.             if j <=newlist[i][1] and j>=newlist[i][0]:
   
8.                 count += 1
   
9.                 temp = j
   
10.             if count == 2:
    
11.                 break
    
12.         if count == 0:
    
13.             result.append((newlist[i][1]-1))
    
14.             result.append(newlist[i][1])
    
15.         if count == 1:
    
16.             if temp !=newlist[i][1]:
    
17.                 result.append(newlist[i][1])
    
18.             else:
    
19.                 result.append(newlist[i][1]-1)
    
20.         count = 0
    
21.     return len(result)

复制代码

扁扁

观摩大佬解答

kylin121380

1. def find(list1):
   
2.     items = list1[:]
   
3.     dic = dict()
   
4.     for i in list1:
   
5.         for j in range(i[0],i[1] + 1):
   
6.             dic.setdefault(str(j),0)
   
7.             dic[str(j)] += 1
   
8.    
   
9.     sort = sorted(dic,key = dic.__getitem__)
   
10.     setlist = [sort.pop()]
    
11.     while items:
    
12.         setlist.append(sort.pop())
    
13.         list1 = items[:]
    
14.         for each in list1:
    
15.             num = 0
    
16.             eachlist = [str(x) for x in range(each[0],each[1] + 1)]
    
17.             for vol in setlist:
    
18.                 if vol in eachlist:
    
19.                     num += 1
    
20.                 if num == 2:
    
21.                     items.remove(each)
    
22.                     break
    
23.     return len(setlist)

复制代码

旅途Z

1. import numpy as np
   
2. import operator
   
3. 
   
4. 
   
5. def get_subset(intervals):
   
6.     intervals = np.array(intervals)
   
7.     interval_num = intervals.shape[0]
   
8.     left_bound = min(intervals[:, 0])
   
9.     right_bound = max(intervals[:, 1])
   
10.     element_dict = {}
    
11.     num_dict = {}
    
12.     length_list = []
    
13.     return_list = []
    
14.     for i in range(interval_num):
    
15.         length_list.append(intervals[i][1]-intervals[i][0]+1)
    
16.     for i in range(left_bound, right_bound+1):
    
17.         for j in range(interval_num):
    
18.             if intervals[j][0] <= i <= intervals[j][1]:
    
19.                 if i not in element_dict:
    
20.                     element_dict[i] = []
    
21.                     num_dict[i] = 0
    
22.                 element_dict[i].append(j)
    
23.                 num_dict[i] += 1
    
24.     sorted_element = sorted(num_dict.items(), key=operator.itemgetter(1), reverse=False)
    
25.     for i in range(len(sorted_element)):
    
26.         for each in element_dict[sorted_element[i][0]]:
    
27.             if length_list[each] == 2:
    
28.                 return_list.append(sorted_element[i][0])
    
29.                 break
    
30.         else:
    
31.             for each in element_dict[sorted_element[i][0]]:
    
32.                 length_list[each] -= 1
    
33.     return len(return_list)
    

复制代码

阴阳神万物主

难度评级：简单
要素分析：数论
随机输入生成器，送给有需要的人：

1. import random
   
2. def gent(a:'区间下限'=1,b:'区间上限'=10,l:'列表长度上限'=4,n:'生成数量'=10):
   
3.     for i in range(n):
   
4.         yield [[(l := random.randint(a,b-1)),random.randint(l+1,b)]for j in range(0,l+1)]
   

复制代码

解题代码：

1. def solve(intervals:list,how:'是否打印最小集合'=False):
   
2.     sets = [set(range(i[0],i[1]+1))for i in intervals]
   
3.     u = set()
   
4.     while sets:
   
5.         n = []
   
6.         l = len(sets)
   
7.         flg = [True]*l
   
8.         for a in range(l-1):
   
9.             for b in range(a+1,l):
   
10.                 c = sets[a].intersection(sets[b])
    
11.                 if len(c)>=2:
    
12.                     if c not in n:n.append(c)
    
13.                     flg[a],flg[b] = False,False
    
14.             if flg[a]:n.append(sets[a])
    
15.         if flg[-1]:n.append(sets[-1])
    
16.         if n == sets:
    
17.             for each in sets:
    
18.                 u = u.union({each.pop(),each.pop()})
    
19.             break
    
20.         sets = n
    
21.     if how:print(u)
    
22.     return len(u)
    
23. if __name__ == '__main__':
    
24.     print('示例1 输出：',solve([[1, 3], [1, 4], [2, 5], [3, 5]]))
    
25.     print('示例2 输出：',solve([[1, 2], [2, 3], [2, 4], [4, 5]]))

复制代码

chen971130

1. def a371(intervals):
   
2.     left = []
   
3.     right = []
   
4.     for i in intervals:
   
5.         left.append(i[0])
   
6.         right.append(i[1])
   
7.     max1 = max(left)
   
8.     min1 = min(right)
   
9.     if max1 > min1:
   
10.         print(max1 - min1 + 3)
    
11.     elif max1 == min1:
    
12.         print('3')
    
13.     else:
    
14.         print('2')
    
15. 
    
16. a371([[1, 3], [1, 4], [2, 5], [3, 5]])
    
17. a371([[1, 2], [2, 3], [2, 4], [4, 5]])

复制代码

钙硼钡锗

1. def f371(intervals):
   
2.     a=[]
   
3.     b=[]
   
4.     for i in intervals:a.append(max(i))
   
5.     m=min(a)
   
6.     for i in intervals:b.append(min(i))
   
7.     n=max(b)
   
8.     print(n-m+3)
   

复制代码

zltzlt

风魔孤行者 发表于 2020-4-8 20:29

解答错误

输入：

1. [[2, 10], [3, 7], [3, 15], [4, 11], [6, 12], [6, 16], [7, 8], [7, 11], [7, 15], [11, 12]]

复制代码

输出：7
预期结果：5

zltzlt

TJBEST 发表于 2020-4-8 20:43
不知道写的对不对，没有严格的证明。试了几个例子是对的

解答错误

输入：

1. [[0, 3], [0, 4], [0, 9], [8, 9], [0, 7], [1, 4], [6, 10], [0, 4], [3, 7], [6, 8]]

复制代码

输出：6
预期结果：5

zltzlt

kinkon 发表于 2020-4-8 20:48
例1的区间是1-5吗？返回1-3好像是最小的啊？

例 1 ？

zltzlt

ouyunfu 发表于 2020-4-8 21:06

解答错误

输入：

1. [[2, 10], [3, 7], [3, 15], [4, 11], [6, 12], [6, 16], [7, 8], [7, 11], [7, 15], [11, 12]]

复制代码

输出：7
预期结果：5

zltzlt

whosyourdaddy 发表于 2020-4-8 23:14

1480 ms