首页 > 试题广场 >

主持人调度（一）

[编程题]主持人调度（一）

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

有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 start_i ,第 i 个活动的结束时间是 end_i ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (start_i,end_i) 这个时间段不能参与其他任何活动。请问一个只有一个主持人能否举办全部活动。

数据范围: $1 \le n \le 10^5$ ， $0 \le start_i,end_i \le 10^9$

示例1

输入

[[0,10],[10,20],[20,30]]

输出

true

示例2

输入

[[0,10],[10,20],[15,30]]

输出

false

算法知识视频讲解

这个算法非得学吗

import java.util.*;

public class Solution {

public static boolean hostschedule(ArrayList<ArrayList<Integer>> schedule) {

Collections.sort(schedule, (a, b) -> a.get(0).compareTo(b.get(0)));

// write code here

for (int i = 0; i < schedule.size() - 1; i++) {

if (schedule.get(i+1).get(0) < schedule.get(i).get(1)) return false;

}

return true;

}

发表于 2023-08-18 17:24:38 回复(0)

C++

一天到晚划水的鱼

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param schedule int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool hostschedule(vector<vector<int> >& schedule) {
        // write code here
        sort(schedule.begin(), schedule.end(), [](vector<int>& v1, vector<int>& v2) {
            return v1[0] < v2[0];
        });
        
        for (int i = 1; i < schedule.size(); ++i) {
            if (schedule[i - 1][1] > schedule[i][0])    return false;
        }
        
        return true;
    }
};

发表于 2022-07-24 21:51:49 回复(0)

C++

牛客487629784号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param schedule int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool hostschedule(vector<vector<int> >& schedule) {
        // write code here
        //将任务按照开始时间递增排序，如果用一个主持人足够
        //那么下一个任务的开始时间必定在上一个任务结束时间之后
        sort(schedule.begin(),schedule.end(),cmp);
        for(int i=1;i<schedule.size();i++)
        {
            if(schedule[i][0]<schedule[i-1][1])
            {
                return false;
            }
        }
        return true;
    }
    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]!=b[0])
        {
            return a[0]<b[0];
        }
        return a[1]<b[1];
    }
};

发表于 2022-07-01 13:40:24 回复(0)

Python 3

呼延棋大宝

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param schedule int整型二维数组 
# @return bool布尔型
#
class Solution:
    def hostschedule(self , schedule: List[List[int]]) -> bool:
        schedule.sort()
        tmp = schedule[0]
        for i in schedule[1:]:
            if i[0] < tmp[1]:
                return False
            else:
                tmp = [tmp[0],i[1]]
        return True
    # write code here

发表于 2023-05-22 12:27:38 回复(0)

小谷围做题家

package main
import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param schedule int整型二维数组 
 * @return bool布尔型
*/
func hostschedule( schedule [][]int ) bool {
    sort.Slice(schedule,func(i,j int)bool{
        return schedule[i][0]<schedule[j][0]
    })
    for i:=1;i<len(schedule);i++{
        if schedule[i-1][1]>schedule[i][0]{
            return false
        }
    }
    return true
}

发表于 2023-03-10 23:46:23 回复(0)

编程小白丁

#include <stdio.h>

int main()

{ int a[][]={{0,10},{10,20},{20,30}};

int count=0;

for(int i=0;i<3;i++)

{ for(int j=1;j<3;j++)

{

if(a[1][i]<=a[0][j])

count++;

}

if(count==2)

printf("true");

else

printf("false")

return 0;

}

发表于 2023-01-11 20:58:12 回复(1)

Python 3

来牛客玩玩

class Solution:
    def hostschedule(self , schedule: List[List[int]]) -> bool:
        # write code here
        return sorted(schedule, key=lambda x: x[1]) == sorted(schedule, key=lambda x: x[0])

发表于 2022-07-08 23:53:33 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

# coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param schedule int整型二维数组
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/e160b104354649b69600803184094adb?tpId=196&tqId=40514&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        同一时间段，支持人只能参加一个活动，问题是一个能否主持所有活动，换句话说就是看所有的活动区间是否重合
        如果不重合：
            返回True；
        否则：
            返回False
    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
    """

    def hostschedule(self, schedule):
        # write code here
        schedule.sort(key=lambda x: x[0])

        end, n = schedule[0][1], len(schedule)
        for i in range(1, n):
            if end > schedule[i][0]:  # 如果前一个活动的结束时间 > 下一个活动的开始时间，说明区间重合，返回False
                return False
            else:
                end = max(end, schedule[i][1]) # 更新活动结束时间

        return True


if __name__ == "__main__":
    sol = Solution()

    # schedule = [[0, 10], [10, 20], [20, 30]]

    schedule = [[0, 10], [10, 20], [15, 30]]

    res = sol.hostschedule(schedule)

    print res

发表于 2022-06-23 16:26:30 回复(0)

Python 3

danspace

class Solution:
    def hostschedule(self , schedule: List[List[int]]) -> bool:
        # write code here
        schedule.sort()
        for i in range(len(schedule)-1):
            e1 = schedule[i][1]
            s2 = schedule[i+1][0]
            if s2 < e1:
                return False        
        return True

发表于 2022-04-22 17:21:55 回复(0)

Python

萌大仙

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param schedule int整型二维数组 
# @return bool布尔型
#
class Solution:
    def hostschedule(self , schedule: List[List[int]]) -> bool:
        # write code here
        schedule.sort()
        for s in range(len(schedule)):
            try:
                if schedule[s+1][0]<schedule[s][1]:
                    return False
            except:
                break
        return True

发表于 2022-04-11 22:36:55 回复(0)

Java

世界杯2009

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param schedule int整型ArrayList<ArrayList<>> 
     * @return bool布尔型
     */
    class InnerModel {
        private int left;
        private int right;
        public InnerModel(int left, int right) {
            this.left = left;
            this.right = right;
        }
        public int getLeft() {
            return left;
        }
        public int getRight() {
            return right;
        }
        @Override
        public String toString() {
            return "[" + left + "," + right + "]";
        }
    }

    public boolean hostschedule(ArrayList<ArrayList<Integer>> schedule) {
        // write code here
        List<InnerModel> total = new ArrayList<>();
        Iterator<ArrayList<Integer>> iterator = schedule.iterator();
        while (iterator.hasNext()) {
            ArrayList<Integer> cur = iterator.next();
            total.add(new InnerModel(cur.get(0), cur.get(1)));
        }
        total.sort(Comparator.comparingInt(InnerModel::getLeft));
        for (int i = 0; i < total.size() - 1; i++) {
            if (total.get(i).getRight() > total.get(i + 1).getLeft()) {
                return false;
            }
        }
        return true;
    }
}

发表于 2022-03-22 22:56:50 回复(0)