首页 > 试题广场 >

牛牛们上班

[编程题]牛牛们上班
  • 热度指数：190 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

在工厂中，有个牛牛工作在一个流水线上，流水线可以看作一个坐标轴，第个牛牛的位置是，延长其手臂的长度为，手臂可以朝向正向和反向，即第个牛牛在流水线的工作范围为，你需要计算最多可以让多少个牛牛同时在流水线上工作且工作范围互不相交（只交在一个点也算相交）。


输入描述:
第一行一个整数，
接下来行，每行个整数 
所有的输入为整数，且 时，.


输出描述:
一行一个整数代表答案
示例1

输入

5
2 3
7 1
5 1
8 3
0 2

输出

2
示例2

输入

4
2 4
4 3
9 3
100 5

输出

2
示例3

输入

5
3 1
8 1
7 3
0 3
4 2

输出

2
算法知识视频讲解
添加回答
zoulam头像 zoulam 
var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let countLine = 0;
let len = 0;
let data = [];
rl.on('line', function (input) {
    if (countLine == 0) {
        len = input.split(' ')[0]
        countLine++
    } else if (countLine <= len) {
        let [val1, val2] = input.split(' ')
        data.push([parseInt(val1), parseInt(val2)])
        countLine++
    }
});

function main(data) {
    for (let i = 0; i < data.length; i++) {
        let [val1, val2] = data[i]
        data[i] = [val1 - val2, val1 + val2]
    }
    data.sort((a, b) => a[0] - b[0])
    let index = 0
    let res = 1
    for (let i = 1; i < data.length; i++) {
        if (data[index][1] >= data[i][0]) {
            if (data[i][1] >= data[index][1]) {

            } else {
                index = i
            }
        } else {
            index = i
            res++
        }
    }
    return res
}

rl.on('close', function () {
    let res = main(data)
    console.log(res)
    process.exit(0);
});

发表于 2021-03-31 22:41:50 回复(0)
张博16头像 张博16 
num=input()
num=int(num)

list2=[] for i in range(num):
    list2.append([int(i) for i in input().split()])

cnt=1 list3=[] for i in list2:
    list3.append((i[0]-i[1],i[0]+i[1])) # 每一次取有边界最小的那个就行了. 所以先按照这个排序即可.   list3=[(i[1],i[0]) for i in list3]
list3.sort()
list3=[(i[1],i[0]) for i in list3] # print(2)  cnt=1 tmp=[]
b=[] if len(list3)>0:
    b=(list3[0])
    list3.pop(0) while(len(list3)>0):
    a=list3[0] if b[1]>=a[0]:
        list3.pop(0) else: # tmp.append(a)  b=a
        cnt+=1  list3.pop(0) print(cnt) # print(2222222)
发表于 2021-02-20 17:23:34 回复(1)
前端成长中头像 前端成长中
这个题目有些没看懂，但是还是总结一下规律写了一下，结果是不正确，有没有大神解答一下的。
    我的想法是，把整体看做一个横坐标，根据第一个数值计算位置，第二个数值计算覆盖范围。
function loop(oArr, index) {
    let resultRange = []
    let result = 0

    for (let i = index, len = oArr.length; i < len; i++) {
        const element = oArr[i];
        if( typeof(element) === 'string' || typeof(element) === 'number' ) {
            // 这是第一行
            resultRange.push([0, element])
            result++
        } else {
            // 这是第n行
            let min = element[0] - element[1]
            min = Math.max(0, min);
            let max = element[0] + element[1]
            let isAdd = true

            for (let j = 0; j < resultRange.length; j++) {
                if(isAdd) {
                    const ele = resultRange[j];
                    if( min <= ele[1] || max <= ele[0]) {
                        isAdd = false
                    }
                }
            }

            if(isAdd) {
                // 可添加
                resultRange.push([min, max])
                result++
            }
        }
    }
    return result;
}


function demo() {
    let result = 0
    for (let index = 0, len = arguments.length; index < len; index++) {
        const res = loop(arguments, index)
        if(res > result) result = res
    }
    return result
}

console.log(demo(5, [2, 3], [7, 1], [5, 1], [8, 3], [0, 2]));
console.log(demo(4, [2, 4], [4, 3], [9, 3], [100, 5]))
console.log(demo(5, [3, 1], [8, 1], [7, 3], [0, 3], [4, 2]))
但是第二个例子，结果是3，目前是认为自己没读懂题目。求大神解

发表于 2021-02-19 16:40:42 回复(0)
提交观点

问题信息

贝壳找房 前端工程师 2021
来自：贝壳找房2023届校招...
上传者：小小
难度：
3条回答 2923浏览

热门推荐

通过挑战的用户

相关试题

牛牛们上班

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号