Binary search on a sorted list of E(startTime,endTime) to find all E's matched by a given time-CodePudding

I have Event objects as follows,

public class Event {
   String name;
   int startTime; // minutes since midnight, e.g 4:15am = 255
   int endTime;   // minutes since midnight, e.g.6:30am = 390
   //   getters/setters
}

They are sorted by startTime ASC,

events.sort(Comparator.comparing(Event::getStartTime));

Events can overlap in any way.

I need to obtain a List of all Events matching (incl. partially) a particular range t1,t2 (also ints for minutes since midnight).

List<Event> eventsMatching = findMatching(t1, t2); // e.g. between 200,205

I don't want to go through the whole list and check e.getStartTime() <= t1 && e.getEndTime() >= t2. Since the list is sorted, I should be able to use Collections.binarySearch() in some way. But normally, a binary search finds the exact object you're looking for: int position = Collections.binarySearch(events, key). Is there some way to find matching ranges quickly using a binary search?

CodePudding user response：

You need to check for all events that meet e.startTime <= t1.

record Event(String name, int startTime, int endTime) {}
List<Event> list = Arrays.asList(
    new Event("a", 2, 3), new Event("b", 3, 4),
    new Event("c", 0, 1), new Event("d", 4, 5));
list.sort(Comparator.comparing(Event::startTime));
System.out.println("sorted:   "   list);
int t1 = 2, t2 = 3;
List<Event> filtered = list.stream()
    .takeWhile(e -> e.startTime() <= t1)
    .peek(e -> System.out.println("checked:  "   e))
    .filter(e -> e.endTime() >= t2)
    .toList();
System.out.println("filtered: "   filtered);

output:

sorted:   [Event[name=c, startTime=0, endTime=1], Event[name=a, startTime=2, endTime=3], Event[name=b, startTime=3, endTime=4], Event[name=d, startTime=4, endTime=5]]
checked:  Event[name=c, startTime=0, endTime=1]
checked:  Event[name=a, startTime=2, endTime=3]
filtered: [Event[name=a, startTime=2, endTime=3]]

CodePudding user response：

Binary search will not help you much, because you're not searching for a single equality-based match, but rather a range or results that can be ordered, but not in a way that's much help to quickly finding matches.

Unless you're dealing with a great many range elements, a linear (ie O(n)) process would work OK.

To speed things up, sort by start date beforehand: Then your iteration over the list would be able to exit early when you encounter an element whose start date to after the target.

CodePudding user response：

You should browse the list and stop when an item is not in range. In terms of complexity, it's the best you can do.

CodePudding user response：

The TreeSet class is an example of a collection that explicitly supports efficient range operators. Because you are searching on two separate ranges (for start and end times) you would likely need 2 sets of events.

TreeSet<Event> startSort = new TreeSet<>(Comparator.comparing(Event::getStart));
TreeSet<Event> endSort = new TreeSet<>(Comparator.comparing(Event::getStart));

Find the events in a given range using headSet, tailSet and subSet. Finding sets of events that satisfy two conditions through finding the intersection of two sets.