В алгоритме расписания Meetup для создания уникальной даты

Question

Я пытался решить этот вопрос, но мне кажется, что я его не очень понимаю. Пожалуйста, не оценивайте меня, я только изучаю алгоритм.

Вопрос: Владелец стартапа ищет новых инвесторов, чтобы получить средства для своей компании. У каждого инвестора жесткий график, который владелец должен соблюдать. Учитывая графики дней, в которые инвесторы доступны, определите, сколько встреч владелец может запланировать. Обратите внимание, что владелец может проводить только одно собрание в день.

Расписания состоят из двух целочисленных массивов: firstDay и lastDay. Каждый элемент в массиве firstDay представляет первый день, в который инвестор доступен, а каждый элемент в lastDay представляет последний день, в который инвестор доступен, включая оба.

Пример:

firstDay = [1,2,3,3,3]

lastDay = [2,2,3,4,4]

Есть 5 инвесторов [I-0, I -1, I-2, I-3, I-4] Инвестор I-0 доступен с 1-го по 2-й день включительно [1, 2] Инвестор I-1 доступен только на 2-й день [2, 2] , Инвестор I-2 доступен только в день 3 [3, 3] Инвесторы I-3 и I-4 доступны только с 3-го дня до 4-го дня [3, 4] Владелец может встретиться только с 4 инвесторами из 5: I-0 в 1-й день, I-1 в 2-й день, I-2 в 3-й день и I-3 в 4-й день. Графики c ниже показывают, что запланированные собрания отмечены зеленым, а заблокированные дни - серым.

Ниже мое текущее решение

Основываясь на том, что я понял до сих пор, это создать простой массив, где Я могу добавить уникальную дату для инвесторов.

<script>


function countMeetings(firstDay, lastDay) {

    let list = [];
    
    firstDay.map(function(item){
    	if(list.indexOf(item)<0) list.push(item);
    });
     
    lastDay.map(function(item){
    	if(list.indexOf(item)<0) list.push(item);
    });
    
    return list.length;
}


console.log(countMeetings([5, 1, 2, 1, 2, 2], [5, 3, 2, 1, 3, 3]));

// output: 4
// expected: 2


</script>

Я ожидал 2, но мой вывод 4.

Answer 1

Я не полностью проверил возможные края, но то, что вы ищете, должно быть вокруг этого.

Итак, наши инвесторы;

var investors = [ {id: 1, ds: [1,2]}
                , {id: 2, ds: [2,2]}
                , {id: 3, ds: [3,3]}
                , {id: 4, ds: [3,4]}
                , {id: 5, ds: [3,4]}
                ];

Первоначально я планировал отсортировать инвесторы в зависимости от продолжительности их доступности, но я думаю, что это избыточно с кодом ниже:

Требуется сортировка. Если мы думаем о случае, как у I-1, есть диапазон дат [1,2], а у I-2 есть диапазон дат [1,1]. В случае, если мы не сортируем, I-1 получает дату 1, занимая только дату I-2. Однако, как только мы сортируем инвесторов в порядке возрастания в зависимости от их доступности, все в порядке.

var is = [ {id: 1, ds: [1,2]}
         , {id: 2, ds: [1,1]}
         , {id: 3, ds: [3,3]}
         , {id: 4, ds: [3,4]}
         , {id: 5, ds: [3,4]}
         ],
    ds = is.sort((a,b) => (a.ds[1]-a.ds[0]) - (b.ds[1]-b.ds[0]))
           .reduce( function(r,o){
                      var day = Array.from({length: o.ds[1] - o.ds[0] + 1}, (_,i) => o.ds[0] + i)
                                     .filter(d => !r[d])[0];
                      return day !== void 0 ? (r[day] = "Investor id: " + o.id, r)
                                            : r;
                    }
                  , {}
                  );
console.log(ds);

.as-console-wrapper {
   max-height: 100% !important
   }

Примечания:

1. ds в investors определяют диапазон. Таким образом, [1,3] будет означать, [1,2,3]
2. day дает первый доступный день, если таковой имеется, или будет undefined
3. day !== void 0 проверок против undefined, так что этот день free.
4. Array.from({length: o.ds[1] - o.ds[0] + 1}, (_,i) => o.ds[0] + i) part создает список из диапазона. Например, [2,5] даст [2,3,4,5]. В этом случае 5 - 2 + 1 = 4 - длина диапазона, и мы начинаем заполнять его начальным индексом 0 + o.ds[0], который равен 2.
5. Когда у нас есть даты, мы проверяем их один за другим против каландра, который является r аргументом в reduce обратном вызове, чтобы увидеть, доступны ли они, я имею в виду undefined. Это .filter(d => !r[d]) часть.
6. Так что day назначается с первой доступной датой или, если ее нет, становится undefined. ([][0] case)
7. Часть return просто заполняет дату с помощью id инвестора, если дата доступна (day !== undefined), или возвращает календарь как есть.