Find maximum time gap between cars in given interval

Given start and end time of all the cars in a given interval, find the maximum time gap in which no car travels.

The start timings are given in sorted order.

Examples:

Input: start[] = { 1, 2, 6 }   end[] = { 3, 5, 9 }
Output: 1
Explanation: 
The first car travels from time unit 1 to 3. 
The second car travels from time unit 2 to 5. 
So at time unit 5, 
the second car stops traveling and hence from 5 to 6, 
no car travels. So the longest gap in which no car travels is (6 - 5) = 1.

Input: start[] = {1, 3, 4} end[] = {10, 8, 6}
Output: 0
Explanation: 
The first car travels from time 1 to 10. 
All the other cars start and stop in between this interval. 
So there is no gap in which no car travels.

Approach:

• Sort the end time array. There is no need to sort the start time array as it is already sorted.
• Take two variables i and j and start traversing both the arrays. Take a variable, namely, car which will store the number of cars currently running.
• If start[i] < end[j], do i = i + 1 and increment cars by 1.
• If start[i] > end[j], decrement cars by 1. If the value of cars become zero, calculate the gap in which no car travels as start[i] – end[j] and compare it with the maximum gap obtained so far i.e. maximum_gap = max( maximum_gap, start[i] – end[j] ). Then make j = j + 1.
• If start[i] == end[j], there is no change in the number of cars running. So make i = i + 1 and j = j + 1.
• Continue the process till i reaches the end of start array.

The C++ code for the above approach is:

#include <bits/stdc++.h>
using namespace std;
// function to find the longest gap
void longestGap(int start[], int end[], int n)
{
    sort(end, end + n); // sort the end timings
    int i = 0, j = 0;
    int cars = 0; // to store the number of cars running
    int maximumGap
        = 0; // to store the maximum gap obtained so far
    while (i < n) {
        if (start[i] < end[j]) {
            cars++;
            i++;
        }
        else if (start[i] > end[j]) {
            cars--;
            if (cars == 0) {
                maximumGap = max(
                    maximumGap,
                    start[i]
                        - end[j]); // update maximum gap
            }
            j = j + 1;
        }
        else // if start[i] == end[j]
        {
            i = i + 1;
            j = j + 1;
        }
    }
    cout << "The maximum gap in which no car travels: "
         << maximumGap;
}
int main()
{

    int start[] = { 1, 2, 6, 10 };
    int end[] = { 3, 6, 7, 12 };
    int n = sizeof(start) / sizeof(start[0]);
    longestGap(start, end, n);
    return 0;
}

Output:

The maximum gap in which no car travels: 3 

Complexity:
The time complexity of the above solution is O(n logn) because of sorting, where n is the size of the array.
The space complexity is O(1).