5

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!

R Karandikar
  • 51
  • 1
  • Sorry, I misread the question. Ignore my previous comment. – user17732522 Feb 25 '22 at 02:46
  • @user17732522, no problem. Could you please guide me? – R Karandikar Feb 25 '22 at 02:53
  • 3
    The optional fourth parameter to `lower_bound` allows you to provide a custom comparator. That custom comparator could just compare the first element of the vector and ignore the other two. But the default comparator will compare all the elements of the vector. So using `INT_MIN` is a way to make sure that `v` compares smaller than a real event vector when the start times are equal. – user3386109 Feb 25 '22 at 02:54
  • @RKarandikar Its just to make sure that you find an item with the first entry equal to `events[i][1]+1`. As mentioned above, a cleaner solution would be a custom comparator that ignores the fields which shouldn't be relevant to the ordering. – user17732522 Feb 25 '22 at 02:56
  • @user3386109, why do we want to compare _smaller_ than a real event vector? – R Karandikar Feb 25 '22 at 03:00
  • Because you're looking for the lower bound. If there are multiple events with the same start time, and `v` compares smaller than some, and larger than others, then `lower_bound` will return an index in the middle of those vectors, not the index of the first. – user3386109 Feb 25 '22 at 03:14
  • @user3386109, ah, that makes sense. So by that logic, if we are using `upper_bound()`, we will have to use `INT_MAX` to return the largest, correct? – R Karandikar Feb 25 '22 at 03:27
  • Yes, that is correct, provided we agree that `upper_bound()` returns the index of the first element of an array whose value is greater than the value being searched. The answers to [this question](https://stackoverflow.com/questions/23554509/rationale-for-stdlower-bound-and-stdupper-bound) may help you understand what I tried to say there :) – user3386109 Feb 25 '22 at 03:28
  • For a given `i` you wish to find the smallest `j` for which `start_time_j >= end_time_i`. Correct? – Cary Swoveland Feb 25 '22 at 05:24
  • Instead of `{events[i][1]+1,INT_MIN,INT_MIN}` for starttime, endtime and value you could use `v={events[i][1]+1,events[i][1]+1,0}`, as the end time is at least the start time and the value is at least 0, is it? When finding an element, the first field starttime has the highest priority, the endtime the second highest priority and the value the least priority. We want to find the event, which fulfills the starttime, but is the first in the two other categories/fields. The +1 assumes that the times are integers and the next event starts at least +1 after the end of the previous event. – Sebastian Feb 25 '22 at 06:43

1 Answers1

0

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";
    }
}
A M
  • 14,694
  • 5
  • 19
  • 44