算法会议室问题及计算重叠时间区间段

悠悠 2022-10-04 13:00 148阅读 0赞

### 算法会议室问题及计算重叠时间区间段 ###

*  1. 会议室问题
 *  2. 计算重叠时间区间段

# 1. 会议室问题 #

package com.zrj.algorithm.test;
    
    import cn.hutool.core.date.DateUtil;
    
    import java.util.Arrays;
    import java.util.Date;
    
    /** * 最小会议室问题 * 先说下题目，输入若干时间区间，计算最小需要会议室数。 * 既给你输入若干形如[begin, end]的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。 * 比如给你输入meetings = [[0,30],[5,10],[15,20]]，算法应该返回 2，因为后两个会议和第一个会议时间是冲突的，至少申请两个会议室才能让所有会议顺利进行。 * * @author zrj * @since 2021/7/16 **/
    public class MinMeetingRooms { 
    
        public static void main(String[] args) { 
            // 最小会议室
            int[][] meetings = { { 0, 30}, { 5, 10}, { 15, 20}, { 15, 35}};
            System.out.println("最小会议室: " + minMeetingRooms(meetings));
    
            // 重叠时间区间数
            Date statTime1 = DateUtil.parse("2021-07-05 01:10:00");
            Date endTime1 = DateUtil.parse("2021-07-05 01:10:30");
    
            Date statTime2 = DateUtil.parse("2021-07-05 01:10:05");
            Date endTime2 = DateUtil.parse("2021-07-05 01:10:10");
    
            Date statTime3 = DateUtil.parse("2021-07-05 01:10:15");
            Date endTime3 = DateUtil.parse("2021-07-05 01:10:20");
    
            Date[][] timePeriod = { { statTime2, endTime2}, { statTime1, endTime1}, { statTime3, endTime3}};
            System.out.println("重叠时间区间数:" + OverlappingTimePeriod(timePeriod));
    
        }
    
        /** * 会议室问题 * 最少需要会议室数，其实就是在找重叠时间区间数 */
        public static int minMeetingRooms(int[][] meetings) { 
            int n = meetings.length;
            int[] begin = new int[n];
            int[] end = new int[n];
            //将左右端点分别放入对应数组
            for (int i = 0; i < n; i++) { 
                begin[i] = meetings[i][0];
                end[i] = meetings[i][1];
            }
            // 左右端点数组排序
            Arrays.sort(begin);
            Arrays.sort(end);
    
            // 统计计数器
            int count = 0;
            // 记录count最大值
            int res = 0;
            // 开始与结束两个端点数组下标
            int i = 0, j = 0;
            while (i < n && j < n) { 
                // 依次比较开始端点数组中的值与结束端点数组中的值
                if (begin[i] < end[j]) { 
                    // 扫描开始端点
                    count++;
                    i++;
                } else { 
                    // 扫描结束端点
                    count--;
                    j++;
                }
                // 记录count中最大值
                res = Math.max(res, count);
            }
            return res;
        }
    
        /** * 重叠时间区间数 */
        public static int OverlappingTimePeriod(Date[][] timePeriod) { 
            int n = timePeriod.length;
            Date[] begin = new Date[n];
            Date[] end = new Date[n];
            for (int i = 0; i < n; i++) { 
                begin[i] = timePeriod[i][0];
                end[i] = timePeriod[i][1];
            }
            Arrays.sort(begin);
            Arrays.sort(end);
    
            int count = 0;
            int res = 0, i = 0, j = 0;
            while (i < n && j < n) { 
                if (DateUtil.compare(begin[i], end[j]) < 0) { 
                    count++;
                    i++;
                } else { 
                    count--;
                    j++;
                }
                res = Math.max(res, count);
            }
            return res;
        }
    
    }

# 2. 计算重叠时间区间段 #

同上