Binary searching for a vector<int> in vector<vector<int>>

Question

I have a vector events, which consists of vector of events, such as:

events = [[1,3,2],[2,4,3],[4,5,2],[10,20,8]]

where events[i] is of the format [startTime_i, endTime_i, value_i] (inclusive). All the events are sorted in such a way that jth event appears after ith, if startTime_j > startTime_i.

Since the events are sorted, I want to use binary search (lower_bound()) to find out the next non-overlapping event that I could attend after the current one.

A friend suggested using:

vector<int> v={events[i][1]+1,INT_MIN,INT_MIN};
auto nextOne=lower_bound(begin(events),end(events),v);

I don't follow the intuition behind setting the 2nd and 3rd values to INT_MIN above. Could someone please explain? If I had to get an upper_bound(), would I have to use INT_MAX instead?

Thank you!

Answer 1

It depends a little bit on your sorting criteria.

You mentioned that the only criterium is "if startTime_j > startTime_i". So a comparison operator for your "Event" struct could be like:

// Simple comparison operator
bool operator < (const Event& other) const { return startTime < other.startTime; }

Only the start Time is taken as criterium for the comparison. In such case, INT_MIN and INT_MIN are just dummies. They will not be used in any comparison for std::lower_bound. And I guess, it is like that because of the first parameter in the "search event". Look at

events[i][1]+1,INT_MIN,INT_MIN

Here we build one Event, wit some dummy value (INT_MIN) for the "endTime" and "value" and with a start time, that is one bigger than the end time of events[i]

To repeat. This means: We search for the next event, where the "startTime" is higer then the "endTime" of the current element.

Example, if the current element is 1,3,2, then the end time is 3. So, if we do not want to have an overlap, we need to look for some element with a start time >= 3+1. And this will be 4,5,2.

That is rather intuitive. And, as said, INT_MIN is just a dummy. It will not be used.

To illustrate how this could work, please see and run the below code:

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

struct Event {
    int startTime{};
    int endTime{};
    int value{};

    // Simple comparison operator
    bool operator < (const Event& other) const { return startTime < other.startTime; }

    // Simple overwrite of inserter operator for easy output
    friend std::ostream& operator << (std::ostream& os, const Event& e) {
        return os << e.startTime << ' ' << e.endTime << ' ' << e.value;
    }
};

int main() {
    // Main Test data
    std::vector<Event> events{ {2,4,3}, {1,3,2},{10,20,8},{4,5,2}};
    std::cout << "\nOriginal:\n";  
    for (const Event& e : events) std::cout << e << '\n';

    // Sort, if not yet sorted
    std::sort(events.begin(), events.end());
    std::cout << "\nSorted:\n";
    for (const Event& e : events) std::cout << e << '\n';

    // For test purposes: Search the next none overlapping event for each event
    for (const Event& e : events) {

        // Build the search event. It shall not overlap. So the start time of the next
        // must be greater than the end time of this
        Event searchEvent = e;
        searchEvent.startTime = e.endTime + 1;

        // Now search the
        std::cout << "\n\nLooking for the next none overlapping element after: " << e << '\n';

        std::vector<Event>::iterator next = std::lower_bound(events.begin(), events.end(), searchEvent);
        if (next != events.end()) {
            std::cout << "Found at index " << std::distance(events.begin(), next) << "   --> " << *next << '\n';
        }
        else std::cerr << "Not found\n";
    }
}