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

Question

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

Given two arrays firstDay and lastDay representing the intervals in days of possible meetings. Calculate the maximum number of meetings, with only one meeting per day.

示例:

输入:

firstDay = [1, 1, 3]; lastDay= [1, 3, 3]

输出:

3

说明:

Array interval[i] = [firstDay[i], lastDay[i]]

在区间[0] = [1, 1]内，本次 session 只能在第1天举行，因此为第1天的 session ；

在间隔 [1] = [1, 3] 中，该 session 可以在第 1、2 或 3 天举行，但是第 1 天已经很忙，第 3 天会干扰间隔 [2]，只留下第 1 天2 次 session ；

在[2] = [3, 3]区间内，本次 session 只能在第3天举行，因此为第3天的 session ；

解决方案:(贪心算法)

    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();
    }

Answer 1

这是另一种贪婪算法。

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

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

这是一个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";
}