0

How to find threads with overlapping times if I have a list of threads with start times and end times? Is there an algorithm for this?

I looked at this and I do not know if this would help since it finds the maximum number of overlaps.

Community
  • 1
  • 1
ArsenalRocks
  • 339
  • 1
  • 4
  • 12

1 Answers1

2

Make an array of Time,(Start|End),ThreadNr objects.

Sort by time. Break ties by preferring Start objects to count endpoints overlaps, or prefer End objects to exclude endpoints overlaps.

Make an "active" array of ThreadNr values.

Make an "overlapping" set of pairs of ThreadNr values.

Walk through the sorted values, and: When encountering a Start, add an entry to the "overlapping" set for ThreadNr paired with each other thread value in the active array, then add the ThreadNr to the active array. When encountering an End, remove the ThreadNr from the active array.

Atsby
  • 2,277
  • 12
  • 14