Проблема регистрации партийного журнала

Question

была вечеринка. Был журнал регистрации, в котором регистрировалось время входа и выхода всех гостей. Вы должны указать время, когда в вечеринке было максимальное количество гостей.входными данными будут время входа и выхода всех n гостей [1,4] [2,5] [9,12] [5,9] [5,12] выходной сигнал будет t = 5, так как было максимум 3guest был там namly guest (начиная с 1) 2,4 и 5.

Я до сих пор пробовал:

main()
        {
    int ret;
    int a[5]={1,2,9,5,5};
    int b[5]={4,6,12,9,12};
    int i,j;
    int runs=5;
    int cur = 0,p1 = 0,p2 = 0;
    printf("input is ");
    for(i=0;i<5;i++)
    {
        printf("(");
        printf("%d,%d",a[i],b[i]);
        printf(")");

    }

    while(runs--)
    {
        while(p1<5 && p2<5)
        {
            if(a[p1] <= b[p2])
            {
                cur ++;
                p1 ++ ;
            }
            else {
                cur --;
                p2 ++ ;
            }
            ret = cur ;
        }
    }
    printf("\n the output is %d",ret);

        }

Я получаю 3 в качестве результата ... что совершенно неправильно!где я делаю ошибку?

Answer 1

Некоторые вещи проблематичны с вашим кодом. Вот несколько советов, как его улучшить:

• Ваш алгоритм сам по себе сомнителен. Предположим, что ваш первый гость является хозяином вечеринки и остается от 1 до времени окончания вечеринки. С вашим текущим кодом p2 никогда не изменится, и вы будете игнорировать время отпуска всех других гостей.

• Даже если ваш алгоритм работает, он предполагает, что ваш вход отсортирован. Итерируя p1 / p2, вы неявно допускаете время нарастания в вашем массиве, что уже неправильно для вашего образца ввода. Таким образом, вы должны сначала отсортировать ввод.

• Вы присваиваете результат ret на каждой итерации вашего основного цикла. Это игнорирует тот факт, является ли текущее состояние (cur) максимальным количеством гостей или нет. Подсказка: если вам нужно вычислить максимум чего-либо, и в вашем коде нет максимальных вычислений, возможно, чего-то не хватает.

Вот другая идея: предполагая, что вы можете сэкономить массив размера maxtime, создайте массив, заполненный нулями. Обработайте ваш ввод, увеличивая массив в определенное время, если гость прибывает, и уменьшайте его, когда гость уходит. Например, первые 5 минут будут выглядеть как [1, 1, 0, -1, 1, ...]. Тогда намного проще проходить линейно по массиву и вычислять максимальную сумму префикса. Кроме того, намного проще вычислить полный интервал времени для того, как долго присутствовало это максимальное количество гостей.

(Если вы хотите стать более необычным и иметь гораздо больший общий временной интервал, вместо того, чтобы полагаться на карту со временем в качестве ключей. Инициализируйте как массив, затем обработайте ключи в отсортированном порядке.)

Answer 2

Вы печатаете индекс вместо фактического времени.Попробуйте напечатать отредактировано p1[ret] a[ret].