时间戳

首页 > 解决方案 > 如何计算可能的最大会议次数

java - 如何计算可能的最大会议次数

问题描述

我正在尝试解决以下面试问题

给定两个数组 firstDay 和 lastDay 代表可能会议的天数。计算最大会议次数，每天只有一次会议。

示例：

输入：

第一天 = [1, 1, 3]; 最后一天= [1, 3, 3]

输出：

3

说明：

数组区间[i] = [firstDay[i], lastDay[i]]

在区间 [0] = [1, 1] 内，本次会议只能在第 1 天召开，所以是第 1 天的会议；

在区间 [1] = [1, 3] 中，可以在第 1、2 或 3 天举行会议，但是第 1 天已经很忙，第 3 天会干扰区间 [2]，只剩下第 2 天会议;

在区间 [2] = [3, 3] 内，本次会议只能在第 3 天召开，所以是第 3 天的会议；

解决方案：（贪心算法）

    public static int countMeetings(List<Integer> firstDay, List<Integer> lastDay) {
        List<Interval> intervals = IntStream.range(0, firstDay.size())
                .mapToObj(i -> new Interval(firstDay.get(i), lastDay.get(i)))
                .sorted(Comparator.comparing(Interval::getEnd))
                .collect(Collectors.toList());

        List<Integer> meetings = new ArrayList<>();
        intervals.forEach(interval -> {
            for (int i = interval.getStart(); i <= interval.getEnd(); i++) {
                if (!meetings.contains(i)) {
                    meetings.add(i);
                    break;
                }
            }
        });

        return meetings.size();
    }

标签： javaalgorithm

解决方案

看一下这个：

可以使用贪心算法解决这个问题：

static int getMaximumMeetings(List<Integer> start, List<Integer> timeTaken) {
    List<Interval> list = new ArrayList<>(); // create a List of Interval
    for (int i = 0; i < start.size(); i++) {
        list.add(new Interval(start.get(i), start.get(i) + timeTaken.get(i)));
    }
    list.sort(Comparator.comparingInt(i -> i.end)); // sort by finish times ascending

    int res = 0;
    int prevEnd = Integer.MIN_VALUE; // finish time of the previous meeting

    for (Interval i : list) {
        if (i.start >= prevEnd) { // is there a conflict with the previous meeting?
            res++;
            prevEnd = i.end; // update the previous finish time
        }
    }
    return res;
}

只是一些 Interval 实体的示例：

class Interval {
    int start;
    int end;    
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

如果您对上述代码有任何疑问，请在下方留言，我随时为您提供帮助。

推荐阅读