挑选代表

[编程题]挑选代表

热度指数：3868 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

我们有很多区域，每个区域都是从a到b的闭区间，现在我们要从每个区间中挑选至少2个数，那么最少挑选多少个？

输入描述:

第一行是N（N<10000）,表示有N个区间，之间可以重复
然后每一行是ai,bi，持续N行，表示现在区间。均小于100000

输出描述:

输出一个数，代表最少选取数量。

示例1

输入

输出

算法知识视频讲解

Python

南瓜风

Python 为什么res用列表就会显示超时

n=int(input())
import sys
data=[]
for i in range(n):
    data.append(list(map(int,sys.stdin.readline().strip().split())))
#区间找点问题,按右端排序
data=sorted(data,key=lambda x:x[1])
res=set()
for i in data:
    count=0
    for k in range(i[0],i[1]+1):
        if k in res:
            count+=1
        if count==2:
            break
    if count==0:
        res.add(i[-1]-1)
        res.add(i[-1])
    if count==1:
        res.add(i[-1])
print(len(res))

发表于 2020-03-26 22:31:29 回复(0)

Python

贾志统

def func(n, sections):
    sections.sort()
    bi = sections[0][0]
    select_nums = [bi - 1, bi]
    for section in sections:
        ai = section[1]
        bi = section[0]
        if ai <= select_nums[-2]:
            continue
        elif ai <= select_nums[-1]:
            select_nums.append(bi)
        else:
            select_nums.append(bi)
            select_nums.append(bi - 1)
    print(len(select_nums))


n = int(input())
sections = []
for i in range(n):
    ai, bi = map(int, input().split())
    per_section = (bi, ai)
    sections.append(per_section)
func(n, sections)

发表于 2019-08-28 15:12:32 回复(0)

Python

欧巴禾

arr = []
n = int(input()) for _ in range(n):  elem = list(map(int, input().split()))
    arr.append(elem)
arr = sorted(arr, key = lambda x :x[1]) if len(arr)==1:  print(2) else:  select = []
    k = range(arr[0][0], arr[0][1]+1)
    select.append(k[-2])
    select.append(k[-1]) for i in range(1, len(arr)):  elem = arr[i]
        right = elem[1]
        left = elem[0]
        count = 0  for j in select:  if j>=left and j<=right:  count +=1  if count==0:  select.append(right-1)
            select.append(right) if count==1:  select.append(right) if count==2:  continue print(len(select))

发表于 2019-08-21 18:47:16 回复(0)

Python

天麟123

import sys

n = sys.stdin.readline().strip()
n = int(n)
temp = []
sol =[]
for i in range(n):
l = list(map(int,sys.stdin.readline().strip().split()))
temp.append(l[::-1])
temp.sort()
sol.append(temp[0][0]-1)
sol.append(temp[0][0])
for i in range(n-1):
if sol[-1]>=temp[i+1][-1] and sol[-2]<temp[i+1][-1]:
sol.append(temp[i+1][0])
elif sol[-1]<temp[i+1][-1]:
sol.append(temp[i+1][0]-1)
sol.append(temp[i+1][0])
print(len(sol))

发表于 2019-03-16 11:20:18 回复(0)