Leetcode 759. Employee Free Time
2024-10-18 01:07:01
思路:区域覆盖问题。一个自然的想法是将每个员工的工作时间段看做一个木棒,每个木棒的长度就是这个时间段的时长。然后按照木棒的起始位置升序排列,接着由低位置向高位置一个木棒一个木棒的看过去。如果当前木棒的末节点的位置>下一个木棒的头节点位置,那么这两个节点就是一个free time的开头和结尾;如果当前木棒的末节点位置<=下一个木棒的头节点位置,那么更新当前木棒的末节点位置为max(当前木棒的末节点位置,下一个木棒的头节点位置)。
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList<>();
PriorityQueue<Interval> pq = new PriorityQueue<>((a,b)->a.start - b.start);//按照第一个元素升序排列
schedule.forEach(e->pq.addAll(e));//lamdba表达式,将schedule的每个元素的每个子元素加入pq中
Interval before = pq.poll();
while(!pq.isEmpty()) {
if(before.end < pq.peek().start) {
res.add(new Interval(before.end, pq.peek().start));
before = pq.poll();
}else{
before = before.end < pq.peek().end ? pq.peek() : before;//这里不能写成before = before.end < pq.peek().end ? pq.poll() : before;会Time Limit Exceeded
pq.poll();
}
}
return res;
}
}
最新文章
- 什么是英特尔&#174; Edison 模块?
- WCF局域网内使用代理无法访问解决方法
- web.xml 中的listener、 filter、servlet 加载顺序
- Codeforces Codeforces Round #316 (Div. 2) C. Replacement 线段树
- JavaScript核心
- iOS开发之SDWebImage详解
- hdu 4656 Evaluation [任意模数fft trick]
- ArrayList迭代器源码分析
- stm32之CMSIS标准、库目录、GPIO
- linux >; 和 >;>; 、<; 区别
- SSH Secure Shell Client中文乱码的解决方法
- 使用ROP攻击绕过Windows的DEP
- 通过DHCP动态管理IP地址
- JS 中 JSON 对象与字符串之间的相互转换
- mac配置--ant
- 如何运行vue项目(从gethub上download的开源项目)
- CentOS中配置xrdp,通过微软远程桌面访问CentOS桌面
- JS 日期 自动补齐 “2017-11-22 14:43”
- (LeetCode 141/142)Linked List Cycle
- 【BZOJ2946】[Poi2000]公共串 后缀数组+二分
热门文章
- linux 各项分布(个人记录)
- eclipse/sublime 等宽字体设置
- Java 理论与实践: 用弱引用堵住内存泄漏
- iOS笔记之UIKit_UINavigationController
- mosh——Linux下基于UDP的SSH连接工具
- .net core 与ELK(1)安装Elasticsearch
- DevExpress中获取GridControl排序之后的List
- 轻量级MVVM框架 Stylet
- 【转】C# 之泛型详解
- How do I convert an IIR filter into a FIR filter in digital signal processing?