贪心算法——会议安排问题

问题描述

公司有N个同等级的会议需要使用同一个会议室，现在给你这个N个会议的开始和结束时间，怎么安排才能找到一个解决方案，使得会议室最大利用？

样例：

4
0 9
8 10
10 12
8 20
Metting{mettingNum=1, startTime=0, endTime=9}
Metting{mettingNum=3, startTime=10, endTime=12}

第一行表示N个会议，下面四行表示会议开始时间和结束时间，最后输出会议安排结果。

代码实现

/**
 * 贪心算法
 * 公司有N个同等级的会议需要使用同一个会议室，现在给你这个N个会议的开始和结束时间，怎么安排才能找到一个解决方案，使得会议室最大利用？
 */
class GreedAlgorithm {

    static class Metting implements Comparable<Metting>{
        int mettingNum;
        int startTime;
        int endTime;

        public Metting(int mettingNum, int startTime, int endTime) {
            this.mettingNum = mettingNum;
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public String toString() {
            return "Metting{" +
                    "mettingNum=" + mettingNum +
                    ", startTime=" + startTime +
                    ", endTime=" + endTime +
                    '}';
        }

        @Override
        public int compareTo(Metting o) {
            if (this.endTime > o.endTime) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    /**
     * 4
     * 0 9
     * 8 10
     * 10 12
     * 8 20
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Metting> mettings = new ArrayList<>();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            Metting metting = new Metting(i + 1, start, end);
            mettings.add(metting);
        }
        mettings.sort(null);
        int curTime = 0; // 从0点开始可以开会
        for (int i = 0; i < n; i++) {
            Metting metting = mettings.get(i);
            if (metting.startTime >= curTime) { // 如果会议的开始时间大于当前时间，表示可以开会
                System.out.println(metting.toString());
                curTime = metting.endTime;
            }
        }

    }
}