Как рассчитать максимально возможное количество встреч

Question

Я пытаюсь решить следующую задачу собеседования

Даны два массива 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();
    }

Answer 1

Вот еще один жадный алгоритм.

Интервалы сортируются по последнему дню, затем, если равенство по первому дню.

Затем для каждого интервала мы пытаемся вставить один дня перерыва в наборе дней встреч. Если нам это удается, мы увеличиваем количество встреч.

Вот реализация на 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";
}

Answer 2

здесь мы go я попробовал очень простым способом, просто введите свой ввод в мой код и попробуйте запустить код, надеюсь, вы получите желаемый 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;
    }
}

If у вас все еще есть проблемы, просто свяжитесь со мной.

Answer 3

Проверьте это:

Эту проблему можно решить с помощью жадного алгоритма:

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

И если у вас есть какие-либо сомнения в приведенном выше коде, просто прокомментируйте, я всегда готов вам помочь.