会议室I
题目
题目链接：
形容给定一系列的会议工夫距离，包含起始和完结工夫[[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
题目
题目链接：
形容给定一系列的会议工夫距离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
题目
题目链接：
形容你有一个以后会议列表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;}本篇文章如有帮忙到您，请给「翎野君」点个赞，感谢您的反对。