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

zltzlt

kylin121380 发表于 2020-4-9 11:22

解答错误

输入：

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

输出：7
预期结果：5

zltzlt

旅途Z 发表于 2020-4-9 13:17

解答错误

输入：

[[60, 92], [69, 113], [90, 101], [8, 48], [60, 101], [22, 47], [16, 43], [6, 45], [66, 78], [23, 113], [14, 45], [31, 90], [97, 121], [17, 21], [47, 66], [14, 72], [94, 96], [85, 90], [21, 49], [34, 73], [38, 85], [42, 91], [58, 114], [6, 110], [32, 100]]

输出：13
预期结果：12

zltzlt

阴阳神万物主 发表于 2020-4-9 17:02
难度评级：简单
要素分析：数论
随机输入生成器，送给有需要的人：

解答错误

输入：[[6, 21], [1, 15], [15, 20], [10, 21], [0, 7]]
输出：6
预期结果：4

zltzlt

chen971130 发表于 2020-4-9 20:17

解答错误

输入：

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

输出：7
预期结果：5

zltzlt

钙硼钡锗 发表于 2020-4-10 09:11

解答错误

输入：

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

发代码应该这样发：https://fishc.com.cn/forum.php?m ... peid%26typeid%3D441

果果夏天

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)

阴阳神万物主

zltzlt 发表于 2020-4-10 13:15
解答错误

输入：[[6, 21], [1, 15], [15, 20], [10, 21], [0, 7]]

修好了

def solve(intervals:list,how:'是否打印最小集合'=False):
    sets = [set(range(i[0],i[1]+1))for i in intervals]
    setses = sets[:]
    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:break
        sets = n
    db = [[j for j in sets if len(j.intersection(i))>=2]for i in setses]
    def rm(a,s):
        i = 0
        while i<len(a):
            if s in a[i]:
                a.pop(i)
            else:
                i+= 1
    while db:
        for each in db:
            if len(each)==1:
                u.update({each[0].pop(),each[0].pop()})
                rm(db,each[0])
                break
        else:
            nd = []
            for each in sets:
                n = 0
                for l in db:
                    if each in l:n += 1
                nd.append((each,n))
            nd.sort(key=lambda x:x[1],reverse=True)
            u.update({nd[0][0].pop(),nd[0][0].pop()})
            rm(db,nd[0][0])
    if how:print(intervals,'->',u)
    return len(u)
if __name__ == '__main__':
    print('示例1 输出：',solve([[1, 3], [1, 4], [2, 5], [3, 5]],1))
    print('示例2 输出：',solve([[1, 2], [2, 3], [2, 4], [4, 5]]))
    print('之前错的：',solve([[6, 21], [1, 15], [15, 20], [10, 21], [0, 7]],1))

776667

from itertools import combinations

def fun371(intervals):
    intervals = [[j for j in range(i[0],i[1]+1)] for i in intervals]
    total = [i for i in range(min(j[0] for j in intervals),max(j[1] for j in intervals)+1)]
    for i in range(2,len(total)+1):
        for j in combinations(total,i):
            for n in intervals:
                count = 0
                for m in j:
                    if m in n:
                        count += 1
                if count < 2:
                    break
            else:
                return len(j)