0

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

给定两个数组 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();
    }
4

3 回答 3

0

看一下这个：

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

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

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

于 2020-05-25T12:13:47.503 回答
0

这是另一个贪心算法。

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

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

这是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";
}
于 2020-05-25T14:28:59.700 回答
0

在这里，我尝试了一种非常简单的方法，只需将您的输入输入我的代码并尝试运行代码，希望您能获得所需的 o/p：

package testui;

import java.util.ArrayList;
import java.util.Arrays;

public class testas {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<Integer> firstDay = new ArrayList<Integer>(Arrays.asList(1,1,3));
        ArrayList<Integer> lastDay = new ArrayList<Integer>(Arrays.asList(1,3,3));

        ArrayList<Interval> lol = new ArrayList<Interval>();
        for(int i=0;i<firstDay.size();i++) {
            lol.add(new Interval(firstDay.get(i),lastDay.get(i)));
        }

        ArrayList<Integer> check = new ArrayList<Integer>();

        for(Interval con : lol) {
            if(!check.contains(conobj.start) || !check.contains(conobj.end)) {
                for(Integer i=conobj.start;i<=conobj.end;i++) {
                    if(!check.contains(i))
                        check.add(i);
                }
            }
        }

        System.out.println(check.size());



    }

}

class Interval{
    Integer start;
    Integer end;

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

如果您仍然有任何问题，请与我联系。

于 2020-05-25T15:43:24.407 回答