java - 如何计算可能的最大 session 数量

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


给定两个数组firstDay和lastDay表示可能的会议间隔天数。计算最大会议数，每天仅召开一次会议。


例：

输入：


firstDay = [1，1，3]; lastDay = [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();
    }

最佳答案

这是另一种贪婪算法。

间隔将根据最后一天进行排序，如果相等，则根据第一天进行排序。

然后，对于每个间隔，我们尝试将间隔的一天插入一天的会议日期中。如果我们成功了，我们将增加会议次数。

这是C ++的实现（对不起，不懂Java。如果不清楚，请告诉我）

#include    <iostream>
#include    <vector>
#include    <set>
#include    <numeric>
#include    <algorithm>

int countMeetings (std::vector<int> &firstDay, std::vector<int> &lastDay) {
    int count = 0;
    int n = firstDay.size();
    std::vector<int> sort_index (n);
    std::iota (sort_index.begin(), sort_index.end(), 0);    // 0, 1, 2, 3, 4
    auto compar = [&firstDay, &lastDay] (int i, int j) {
        if (lastDay[i] != lastDay[j]) return lastDay[i] < lastDay[j];
        else return firstDay[i] < firstDay[j];
    };
    std::sort (sort_index.begin(), sort_index.end(), compar);

    std::set<int> meetings;

    for (auto i: sort_index) {      // we examine all intervals
        for (int j = firstDay[i]; j <= lastDay[i]; j++) {       // we examine all days of the intervl
            if (meetings.find(j) == meetings.end()) {       // j is a possible meeding date
                count++;
                meetings.insert (j);
                break;
            }
        }
    }

    return count;
}

int main() {
    std::vector<int> firstDay = {1, 2, 3, 3, 3};
    std::vector<int> lastDay= {2, 2, 3, 4, 4};
    int count = countMeetings (firstDay, lastDay);
    std::cout << "number of meetings = " << count << "\n";
}