Объединение перекрывающихся интервалов на основе максимального количества гостей - PullRequest
Новая
       34

Объединение перекрывающихся интервалов на основе максимального количества гостей

1 голос
/ 18 мая 2019

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

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

Я попытался добавить время, приходящее из времени и времени2, в один список и отсортировать его, но он добавляет слишком много значений для некоторых тестовых входов. 

int max = 1; int count = 1; 
int i = 1; int j = 0; 
long time = arrival[0]; long time2= dep[0];

        while (i < n1 && j < n1) // n1 is the length of the input integer
        {
            if (arrival[i] < dep[j])
            {
                count++;

                if (count >= max)
                {
                    max = count;  
                    time = arrival[i];  
                    time2= dep[j];                 
                }   

        // possible location of console.writeline(time1 + time2)     
        // somewhere here I would add time and time2 to a new list

             i++;              
            }

            else
            {
                count--;
                j++;
            }
        } Console.WriteLine(max); Console.WriteLine(time1 + " " + time2);

Итак, скажем, мой ввод 5 гостей с интервалами: (12,30), (18,25), (25,40), (13,15) и (32,36) желаемый результат будет

2 // максимальное количество гостей в то время

13 15 // новая строка для каждого интервала

18 30

32 36

Но я не могу заставить его работать, он показывает только 32-36. Если я помещу console.writeline в возможное место, это даст мне: 13-15, 18-25, 25-30, 32-36. При других тестовых входах с большим количеством дубликатов (например, от 0 до 5 появляется более одного раза в списке), это дает мне слишком много интервалов.

1 Ответ

1 голос
/ 20 мая 2019

Создание массива или списка структур, содержащих время прибытия и отправления для всех гостей, вместе с флагом +1/-1, обозначающим тип события (+1 для прибытия).

Сортировка списка по полю времени.В случае ничьей ставьте событие прибытия первым, если вы хотите зарегистрировать двух гостей с нулевым интервалом (один входит, другой выходит одновременно), или же вылетите первым в противном случае - кажется, ваш случай.

Сделать Count = 0и MaxCount.

Просмотрите список, добавив поле флага к Count.

Значение Count после каждого события обозначает количество квестов в комнате. 

Guests  (12,30), (18,25), (25,40), (13,15) and (32,36)
Events     12;1   13;1   15;-1   18;1   25;-1   25;1  30;-1  32;1   36;-1   40;-1
Count  0      1      2       1      2       1      2      1     2       1       0  
                     ^       x      ^       x      ^      x     ^       x
Max intervals (^-x)

Когда Count достигает MaxCount - начать новый выходной интервал, когда он становится MaxCount - 1 - завершить этот интервал и добавить его к OutList

Когда Count превышает MaxCount - очистить OutList, сделать MaxCount - Count и начать новый выходной интервал

В конце вывести MaxCount и интервалы от OutList

...