[C language brush leetcode] 2332. The latest time to get on the bus (m)

【

I'll give you a subscript from 0  Start length is n  Array of integers for  buses , among  buses[i]  It means the first one i  The departure time of the bus . And give you a subscript from 0  Start length is m  Array of integers for  passengers , among  passengers[j]  It means the first one  j  Arrival time of passengers . All buses leave at different times , All passengers arrive at different times .

Give you an integer  capacity , Means every bus   most   The number of passengers that can be accommodated .

Every passenger will take the next bus with seats . If you are in the y  The time has come , The bus is  x  Set out at all times , Satisfy  y <= x   And the bus is not full , Then you can take this bus . Earliest   Arriving passengers get on the bus first .

Return to the latest time you can arrive at the bus stop by bus . you You can't   Arrive at the same time as other passengers .

Be careful ： Array  buses and  passengers  It doesn't have to be orderly .

Example 1：

Input ：buses = [10,20], passengers = [2,17,18,19], capacity = 2
Output ：16
explain ：
The first 1 A bus carries 1 Passengers .
The first 2 A bus will take you and number 2 Passengers .
Note that you cannot arrive at the same time as other passengers , So you must arrive before the second passenger .
Example 2：

Input ：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
Output ：20
explain ：
The first 1 A bus carries 4 Passengers .
The first 2 A bus carries 6 Position and number 2 Passengers .
The first 3 A bus carries 1 Passengers and you .
 

Tips ：

n == buses.length
m == passengers.length
1 <= n, m, capacity <= 105
2 <= buses[i], passengers[i] <= 109
buses  The elements in Different from each other  .
passengers  The elements in Different from each other

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/the-latest-time-to-catch-a-bus
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

】

This problem has too many conditional branches , It's easy to make a mistake , And the array is not ordered , So first sort the two arrays .

Then I need to sort out the logical relationship of riding ：

Passengers leave earlier than the current train

        The current car is full

                It's the last one ：break

                There's a car in the back ： Take the back car

        There are still seats available in the current car ： Normal multiplication

Passengers are later than the current departure time

        There's a car in the back ： Take the back car

        There is no car in the back ：break

The code sucks , Always patching , It's finally passed , It needs to be optimized later

int Cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int latestTimeCatchTheBus(int* buses, int busesSize, int* passengers, int passengersSize, int capacity){
    int bidx = 0; //  Current vehicle index 
    int lastidx = -1; //  Index of the last passenger's car 
    int lastp = -1;
    int i, j;
    int cnt = 0; //  The number of people currently loaded 
    int flag = 0;
    int ret;

    qsort(buses, busesSize, sizeof(int), Cmp);
    qsort(passengers, passengersSize, sizeof(int), Cmp);

    for (i = 0; i < passengersSize; i++) {
        if (cnt == capacity) { //  The car is full 
            if (bidx < busesSize - 1) { //  If there's a car , Then the next one 
                bidx++;
                cnt = 0;
            } else { //  There is no car in the back 
                flag = 1; //  The current car is full , And there is no car behind , The passenger didn't get on the bus 
                break;
            }
        }

        //  Passengers are later than the current train , And there is a car behind , Then wait for the next one 
        while (passengers[i] > buses[bidx]) {
            if (bidx < busesSize - 1) { //  If there's a car , Judge the time of the next French car   and   Current passenger arrival time 
                bidx++;
                cnt = 0;
            } else { //  There is no car in the back , Current passengers arrive later than all trains 
                flag = 2;
                break;
            }
        }

        if (flag == 2) { //  Jump out of for loop 
            break;
        }

        cnt++; //  Come here , It means that the passengers get on the train 
        lastidx = bidx;
        lastp = i;
        flag = 3; //  Get on the bus normally 
    }

    if (lastp == -1) { //  None of the passengers got on the bus 
        return buses[busesSize - 1];
    }

    if (flag == 2 && passengers[lastp] != buses[busesSize - 1]) { //  The last passenger on board is not the last 
        return buses[busesSize - 1]; //  According to the time of the last bus 
    }

    if ((flag == 3) && ((cnt < capacity) || (bidx < busesSize -1))) { //  It means that all passengers have got on , And the car still has a place 
        if (passengers[lastp] != buses[busesSize - 1]) { //  The last passenger's time is earlier than the last departure time 
            return buses[busesSize - 1]; //  According to the time of the last bus 
        } 
    }

    if (cnt < capacity && passengers[lastp] != buses[lastidx]) { //  The last passenger's car has a vacant seat and is earlier than the departure time 
        return buses[lastidx]; //  Return to the departure time of the previous train 
    }

    //  Come here , It means that the last passenger just filled the last bus 
    ret = passengers[lastp] - 1; //  I have to arrive earlier than the last passenger 
    for (j = lastp - 1; j >= 0; j--) {
        if (ret != passengers[j]) { //  The same time , Only earlier 
            break;
        }

        ret = ret - 1;
    }
   
    return ret;
}

/*
 a key 
1,for Be careful at the circulation , If ahead of time break,i= User index , If you don't break,i =  User index +1
2.  Next car ,cnt To clear , Both codes need 
3. flag=2 when , The last passenger on the train is not the last one 
4.  None of the passengers got on the bus 
*/