面试算法58：日程表

2023-12-18 19:04

文章标签 算法面试 58 日程表

本文主要是介绍面试算法58：日程表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

请实现一个类型MyCalendar用来记录自己的日程安排，该类型用方法book（int start，int end）在日程表中添加一个时间区域为[start，end）的事项（这是一个半开半闭区间）。如果[start，end）中之前没有安排其他事项，则成功添加该事项并返回true；否则，不能添加该事项，并返回false。
例如，在下面的3次调用book方法中，第2次调用返回false，这是因为时间[15，20）已经被第1次调用预留了。由于第1次占用的时间是一个半开半闭区间，并没有真正占用时间20，因此不影响第3次调用预留时间区间[20，30）。
在这里插入图片描述

分析

如果待添加的事项占用的时间区间是[m，n），就需要找出开始时间小于m的所有事项中开始最晚的一个，以及开始时间大于m的所有事项中开始最早的一个。如果待添加的事项和这两个事项都没有重叠，那么该事项可以添加在日程表中。

解

public class MyCalendar {private TreeMap<Integer,Integer> events;public MyCalendar(){events = new TreeMap<>();}public static void main(String[] args) {MyCalendar cal = new MyCalendar();System.out.println(cal.book(10, 20));System.out.println(cal.book(15, 25));System.out.println(cal.book(20, 30));}public boolean book(int start,int end){// 地板：返回键小于或等于给定值的最大映射，如果没有则返回nullMap.Entry<Integer,Integer> event = events.floorEntry(start);if (event != null && event.getValue() > start){return false;}// 天花板：返回键大于或等于给定值的最小映射，如果没有则返回nullevent = events.ceilingEntry(start);if (event != null && event.getKey() < end){return false;}events.put(start,end);return true;}
}