[已解决]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

def func371(intervals):
    count = 0
    newlist = sorted(intervals,key = lambda s:s[1])
    result = [(newlist[0][1]-1),newlist[0][1]]
    for i in range(1,len(newlist)):
        for j in result:
            if j <=newlist[i][1] and j>=newlist[i][0]:
                count += 1
                temp = j
            if count == 2:
                break
        if count == 0:
            result.append((newlist[i][1]-1))
            result.append(newlist[i][1])
        if count == 1:
            if temp !=newlist[i][1]:
                result.append(newlist[i][1])
            else:
                result.append(newlist[i][1]-1)
        count = 0
    return len(result)

跳转到最佳答案楼层

风魔孤行者

def f(i):
    min1 = i[0][0]
    max1 = i[0][1]
    for each in i:
        if each[0]>min1:
            min1 = each[0]
        if each[1]<max1:
            max1 = each[1]
    if max1-min1>=1:
        return 2
    else:
        return min1-max1+3

TJBEST

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

def fun371(intervals):
    def inner(eachSeg):
        result = 0
        index = 0
        M = len(eachSeg)
        Tail = 0
        while index < M - 1:
            state = False
            for innerindex in range(index+1,M):
                if eachSeg[index][1] > eachSeg[innerindex][0]:
                    state = True
                else:
                    break
            else:
                innerindex += 1
            if state == True:
                result += 2
            else:
                result += 2 - Tail
            if innerindex == M:
                break
            else:
                if eachSeg[index][1] == eachSeg[innerindex][0]:
                    Tail = 1
                else:
                    Tail = 0
                index = innerindex
        else:
            result += 2 - Tail
        return result           
    sortedArr = sorted(intervals)
#第一次保留子集
    M = len(sortedArr)
    for index in range(M-1,0,-1):
        if sortedArr[index][0] == sortedArr[index-1][0]:
            del sortedArr[index]
#第二次保留子集，并分组
    Seg = []
    temp = []
    for each in sortedArr:
        if temp != []:
            N = len(temp)
            for index in range(N-1,-1,-1):
                if each[1] <= temp[index][1]:
                    del temp[index]
                else:
                    break
            if temp == [] or each[0] <= temp[-1][1]:
               temp.append(each)
            else:
                Seg.append(temp)
                temp = [each]
        else:
           temp.append(each)
    else:
        Seg.append(temp)
#计算每一个分组的值进行叠加
    result = 0
    for each in Seg:
        result += inner(each)
    return result

kinkon

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

ouyunfu

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

TJBEST

@zltzlt intervals 是否排好序了？

永恒的蓝色梦想

前排

zltzlt

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

不一定

whosyourdaddy

def func371(intervals):
    count = 0
    newlist = sorted(intervals,key = lambda s:s[1])
    result = [(newlist[0][1]-1),newlist[0][1]]
    for i in range(1,len(newlist)):
        for j in result:
            if j <=newlist[i][1] and j>=newlist[i][0]:
                count += 1
                temp = j
            if count == 2:
                break
        if count == 0:
            result.append((newlist[i][1]-1))
            result.append(newlist[i][1])
        if count == 1:
            if temp !=newlist[i][1]:
                result.append(newlist[i][1])
            else:
                result.append(newlist[i][1]-1)
        count = 0
    return len(result)

扁扁

观摩大佬解答

kylin121380

def find(list1):
    items = list1[:]
    dic = dict()
    for i in list1:
        for j in range(i[0],i[1] + 1):
            dic.setdefault(str(j),0)
            dic[str(j)] += 1
    
    sort = sorted(dic,key = dic.__getitem__)
    setlist = [sort.pop()]
    while items:
        setlist.append(sort.pop())
        list1 = items[:]
        for each in list1:
            num = 0
            eachlist = [str(x) for x in range(each[0],each[1] + 1)]
            for vol in setlist:
                if vol in eachlist:
                    num += 1
                if num == 2:
                    items.remove(each)
                    break
    return len(setlist)

旅途Z

import numpy as np
import operator


def get_subset(intervals):
    intervals = np.array(intervals)
    interval_num = intervals.shape[0]
    left_bound = min(intervals[:, 0])
    right_bound = max(intervals[:, 1])
    element_dict = {}
    num_dict = {}
    length_list = []
    return_list = []
    for i in range(interval_num):
        length_list.append(intervals[i][1]-intervals[i][0]+1)
    for i in range(left_bound, right_bound+1):
        for j in range(interval_num):
            if intervals[j][0] <= i <= intervals[j][1]:
                if i not in element_dict:
                    element_dict[i] = []
                    num_dict[i] = 0
                element_dict[i].append(j)
                num_dict[i] += 1
    sorted_element = sorted(num_dict.items(), key=operator.itemgetter(1), reverse=False)
    for i in range(len(sorted_element)):
        for each in element_dict[sorted_element[i][0]]:
            if length_list[each] == 2:
                return_list.append(sorted_element[i][0])
                break
        else:
            for each in element_dict[sorted_element[i][0]]:
                length_list[each] -= 1
    return len(return_list)

阴阳神万物主

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

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

解题代码：

def solve(intervals:list,how:'是否打印最小集合'=False):
    sets = [set(range(i[0],i[1]+1))for i in intervals]
    u = set()
    while sets:
        n = []
        l = len(sets)
        flg = [True]*l
        for a in range(l-1):
            for b in range(a+1,l):
                c = sets[a].intersection(sets[b])
                if len(c)>=2:
                    if c not in n:n.append(c)
                    flg[a],flg[b] = False,False
            if flg[a]:n.append(sets[a])
        if flg[-1]:n.append(sets[-1])
        if n == sets:
            for each in sets:
                u = u.union({each.pop(),each.pop()})
            break
        sets = n
    if how:print(u)
    return len(u)
if __name__ == '__main__':
    print('示例1 输出：',solve([[1, 3], [1, 4], [2, 5], [3, 5]]))
    print('示例2 输出：',solve([[1, 2], [2, 3], [2, 4], [4, 5]]))

chen971130

def a371(intervals):
    left = []
    right = []
    for i in intervals:
        left.append(i[0])
        right.append(i[1])
    max1 = max(left)
    min1 = min(right)
    if max1 > min1:
        print(max1 - min1 + 3)
    elif max1 == min1:
        print('3')
    else:
        print('2')

a371([[1, 3], [1, 4], [2, 5], [3, 5]])
a371([[1, 2], [2, 3], [2, 4], [4, 5]])

钙硼钡锗

def f371(intervals):
    a=[]
    b=[]
    for i in intervals:a.append(max(i))
    m=min(a)
    for i in intervals:b.append(min(i))
    n=max(b)
    print(n-m+3)

zltzlt

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

解答错误

输入：

[[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
不知道写的对不对，没有严格的证明。试了几个例子是对的

解答错误

输入：

[[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

解答错误

输入：

[[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