百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

会议室919、920、1897 会议室电子屏

yuyutoo 2024-10-12 01:24 4 浏览 0 评论

会议室I

题目


题目链接:LintCode 炼码


描述
给定一系列的会议时间间隔,包括起始和结束时间[[s1,e1],[s2,e2],…(si < ei),确定一个人是否可以参加所有会议。

样例1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: false
解释:
(0,30), (5,10) 和 (0,30),(15,20) 这两对会议会冲突

样例2
输入: intervals = [(5,8),(9,15)]
输出: true
解释:
这两个时间段不会冲突


解答


/**
 * 920
 * 给定一系列的会议时间间隔,包括起始和结束时间[[s1,e1],[s2,e2],…(si < ei),确定一个人是否可以参加所有会议。
 *
 * @param intervals: an array of meeting time intervals
 * @return: if a person could attend all meetings
 */
public boolean canAttendMeetings(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) {
        return true;
    }

    Collections.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    });

    int end = intervals.get(0).getEnd();

    for (int i = 1; i < intervals.size(); i++) {
        if (intervals.get(i).getStart() < end) {
            return false;
        }

        // 1,7  8,10
        //end = Math.max(end, intervals.get(i).getEnd());
        end = intervals.get(i).getEnd();
    }

    return true;
}



会议室II


题目


题目链接:LintCode 炼码


描述
给定一系列的会议时间间隔intervals,包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei),找到所需的最小的会议室数量。

样例1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)

样例2
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了


解答


/**
 * 919
 * 给定一系列的会议时间间隔intervals,包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei),
 * 找到所需的最小的会议室数量。
 *
 * @param intervals: an array of meeting time intervals
 * @return: the minimum number of conference rooms required
 */
public int minMeetingRooms(List<Interval> intervals) {

    if (intervals == null || intervals.size() == 0) {
        return 0;
    }

    Collections.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    });

    PriorityQueue<Integer> endTimeList = new PriorityQueue<>();
    endTimeList.offer(intervals.get(0).getEnd());

    for (int i = 1; i < intervals.size(); i++) {
        if (intervals.get(i).getStart() >= endTimeList.peek()) {
            endTimeList.poll();
        }
        endTimeList.offer(intervals.get(i).getEnd());
    }

    return endTimeList.size();
}



会议室III


题目


题目链接:LintCode 炼码


描述
你有一个当前会议列表intervals,里面表明了每个会议的开始和结束时间,以及一些会议室rooms。现在有一系列会议ask需要加入,逐个判断他们能否被安排进当前的会议列表中而不产生冲突。一个会议室在同一时间只能进行一场会议。每个询问都相互独立。

被安排的会议可以拆分。如果需要安排一个[2, 4]的会议,你可以把它分成[2, 3]和[3, 4]两段来进行。

例 1:
输入:
Intervals:[[1,2],[4,5],[8,10]],rooms = 1,ask: [[2,3],[3,4]]
输出: 
[true,true]
解释:
对于[2,3]的询问,我们可以安排一个会议室room0。
以下是room0的会议列表:
[[1,2],[2,3],[4,5],[8,10]]
对于[3,4]的询问,我们可以安排一个会议室room0。
以下是room0的会议列表:
[[1,2],[3,4],[4,5],[8,10]]

例 2:
输入:
[[1,2],[4,5],[8,10]]
1
[[4,5],[5,6]]
输出:
[false,true]


解答


/**
 * 1897
 * 你有一个当前会议列表intervals,里面表明了每个会议的开始和结束时间,以及一些会议室rooms。现在有一系列会议ask需要加入,逐个判断他们能否被安排进当前的会议列表中而不产生冲突。一个会议室在同一时间只能进行一场会议。每个询问都相互独立。
 * <p>
 * 被安排的会议可以拆分。如果需要安排一个[2, 4]的会议,你可以把它分成[2, 3]和[3, 4]两段来进行。
 *
 * @param intervals: the intervals
 * @param rooms:     the sum of rooms
 * @param ask:       the ask
 * @return: true or false of each meeting
 */
public boolean[] meetingRoomIII(int[][] intervals, int rooms, int[][] ask) {

    // 1.汇总统计每个会议的开始时间和结束时间对应的数量
    Map<Integer, Integer> sumMap = new HashMap<>();
    for (int[] interval : intervals) {
        sumMap.put(interval[0], sumMap.getOrDefault(interval[0], 0) + 1);
        sumMap.put(interval[1], sumMap.getOrDefault(interval[1], 0) - 1);
    }

    // 2.将开始结束时间归并到同一个列表中
    List<int[]> originalList = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : sumMap.entrySet()) {
        originalList.add(new int[]{entry.getKey(), entry.getValue()});
    }

    // 3.列表中的时间按先后顺序排序
    Collections.sort(originalList, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];
        }
    });

    int preNum = 0;
    List<int[]> invalidList = new ArrayList<>();

    // 4.当前时间段内还能否再被插入新的会议
    for (int i = 0; i < originalList.size(); i++) {
        int[] v = originalList.get(i);
        preNum += v[1];
        // 当前时间点内的会议室全部被占满了
        if (preNum == rooms) {
            // 被安排的会议可以拆分。如果需要安排一个[2, 4]的会议,你可以把它分成[2, 3]和[3, 4]两段来进行。
            // 以最小单位放入
            invalidList.add(new int[]{v[0], originalList.get(i + 1)[0]});
        }
    }

    // 5.构建返回结果
    boolean[] ans = new boolean[ask.length];
    if (invalidList.size() == 0) {
        Arrays.fill(ans, true);
        return ans;
    }

    for (int i = 0; i < ask.length; i++) {
        // 寻找到 invalidList.get(i)[1] 大于 ask[i][0]
        // 在无效会议区间中找到一个结束时间,比,当前要加入的会议的开始时间,要大的位置
        // 这段无效不能加入的区间还没结束,你却想加入进来
        int index = helper(invalidList, ask[i]);

        // |________|
        //
        if (index != invalidList.size() && invalidList.get(index)[0] < ask[i][1]) {
            // 当前无效的不能加入的会议时间区间开始时间 < 请求加入的会议室的结束时间
            ans[i] = false;
        } else if (index != 0 && invalidList.get(index - 1)[1] > ask[i][0]) {
            ans[i] = false;
        } else {
            ans[i] = true;
        }
    }

    return ans;
}

/**
 * 使用二分查找 寻找到 pos.get(i)[1] 大于 one[0]
 *
 * @param pos
 * @param one
 * @return
 */
public int helper(List<int[]> pos, int[] one) {
    int left = 0;
    int right = pos.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;

        if (pos.get(mid)[1] > one[0]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}



本篇文章如有帮助到您,请给「翎野君」点个赞,感谢您的支持。


首发链接:会议室919、920、1897 - 翎野君 - 博客园



?

相关推荐

YAML配置文件简介及使用(yaml 配置)

简介YAML是"YAMLAin'taMarkupLanguage"(YAML不是一种标记语言)的缩写。相比JSON格式的方便。...

教你如何解决最常见的58种网络故障排除方法

1.故障现象:网络适配器(网卡)设置与计算机资源有冲突。分析、排除:通过调整网卡资源中的IRQ和I/O值来避开与计算机其它资源的冲突。有些情况还需要通过设置主板的跳线来调整与其它资源的冲突。2.故障现...

一分钟带你了解服务器网卡(服务器网卡怎么用)

今天小编和大家聊一下服务器的网卡。什么是网卡?简单说网卡就是计算机与局域网互连的设备。计算机主要通过网卡接入网络。网卡又称为网络适配器或网络接口卡NIC(NetworkinterfaceCard)...

linux文件之ssh配置文件的含义与作用

ssh远程登录命令是操作系统(包括linux和window系统)下常用的操作命令,可以帮助用户,远程登录服务器系统,查看,操作系统相关信息。linux系统对于ssh命令有专门保存其相关配置的目录和文件...

Cilium 官方文档翻译 - IPAM(二)Kubernetes Host模式

KubernetesHostScopeciliumIPAM的kuberneteshost-scope模式通过选项ipam:kubernetes开启,将集群IP地址分配委托给每个独立的节点,并...

域名劫持跳转,域名劫持跳转的解决办法只需5步

简单来说,域名劫持就是把原本准备访问某网站的用户,在不知不觉中,劫持到仿冒的网站上,例如用户准备访问某家知名品牌的网上商店,黑客就可以通过域名劫持的手段,把其带到假的网上商店,同时收集用户的ID信息和...

Linux基本命令(linux基本命令总结)

...

Linux 磁盘和文件系统管理(linux磁盘管理fdisk)

1检测并确认新硬盘...

windows host文件怎么恢复?局域网访问全靠这些!

windowshost文件怎么恢复?windowshost文件是常用网址域名及其相应IP地址建立一个关联文件,通过这个host文件配置域名和IP的映射关系,以提高域名解析的速度,方便局域网用户使用...

Nginx配置文件详解与优化建议(nginx 配置详解)

1、概述今天来详解一下Nginx的配置文件,以及给出一些配置建议,希望能对大家有所帮助。...

Mac电脑hosts文件锁定,如何修改hosts文件权限

有时候我们需要修改hosts文件,但是网上很多教程都行不通,使用sudo命令也不行。其实有一个很简单的方法。打开终端命令行,使用如下命令即可:sudochflags-hvnoschg/etc/...

windows电脑如何修改hosts文件?(windows 修改hosts文件)

先来简单说下电脑host的作用hosts文件的作用:hosts文件是一个用于储存计算机网络中各节点信息的计算机文件;作用是将一些常用的网址域名与其对应的IP地址建立一个关联“数据库”,当用户在浏览器中...

Vigilante恶意软件行为怪异:修改Hosts文件以阻止受害者访问盗版网站

Sophos刚刚报道了一款名叫Vigilante的恶意软件,但其行为却让许多受害者感到不解。与其它专注于偷密码、搞破坏、或勒索赎金的恶意软件不同,Vigilante会通过修改Hosts文件...

hosts文件无法修改几种现象和解决方法

第一种、hosts文件修改完不是直接保存而是弹出另存为窗口解决:1、右击hosts文件——属性——把“只读”前面勾去掉。第二种、打开hosts文件时提示“你没有权限打开该文件,请向文件的所有者或管理员...

hosts文件位置在哪里,教你hosts文件位置在哪里

Hosts是一个没有扩展名的系统文件,其基本作用就是将一些常用的网址域名与其对应的IP地址建立一个关联"数据库",当用户在浏览器中输入一个需要登录的网址时,系统会首先自动从Hosts文件中寻找对应的I...

取消回复欢迎 发表评论: