max - c++ intervals where nobody worked

Question

So i have a m*2 matrix of people's working days

First column is the first day of work and the Second column is the end of the work

Its sorted by the first day

Example:

1 5 1000
2 4 500
3 6 100
10 12 100
14 15 100

I am trying to get the intervals where nobody worked

Here in this example its

7 9
13 13

Here's how i tried:

    int bent = 1;
int i = 1,j = 0;

while(i < m && j < m){
    if(rend[i][0] <= rend[j][1]){
        bent++;
        i++;
    }
    else{
        bent--;
        j++;
    }
    if(bent == 0){
        cout<<rend[j][0]<<" "<<rend[i][1]<<endl;
    }
}

Answer 1

1. Separate each data about work into two events: "start of work" and "end of work".
2. Add each events to a vector and sort by time.
3. Track the change in number of people at work.
4. Obtain the maximum number.

#include <iostream>
#include <vector>
#include <algorithm>

struct worker_data {
    int first_day;
    int end_day;
    int something;
};

struct event_data {
    int time;
    int delta;

    bool operator<(const event_data& e) const {
        if (time != e.time) return time < e.time; // earlier event comes first
        return delta < 0 && e.delta > 0; // if events occur at the same day, end event comes first
    }
};

int main(void) {
    std::vector<worker_data> workers = {
        {1, 5, 1000},
        {2, 4, 500},
        {3, 6, 100},
        {10, 12, 100},
        {14, 15, 100}
    };

    std::vector<event_data> events;
    for (const auto& w : workers) {
        events.push_back({w.first_day, 1}); // add "start of work" event
        events.push_back({w.end_day + 1, -1}); // add "end of work" event
    }
    std::sort(events.begin(), events.end());

    int max = 0, current = 0;
    for (const auto& e : events) {
        current += e.delta;
        if (current > max) max = current;
    }

    std::cout << max << std::endl;

    return 0;
}