0

I need to build an algorithm to merge time intervals from multiple arrays (for simplification considering only one date) while keeping input id information. What are some approaches to do it?

Input:

{"input_id": "1", "ranges": [{"from": 07:00, "to": 13:00}, {"from": 15:00, "to": 15:30}], 
{"input_id": "2", "ranges": [{"from": 08:00, "to": 14:30}]}

Expected output:

{"ranges":[
{"from": 07:00, "to": 08:00, "inputs": [1]},
{"from": 08:00, "to": 13:00, "inputs": [1,2]},
{"from": 13:00, "to": 14:30, "inputs": [2]},
{"from": 15:00, "to": 15:30, "inputs": [1]},
]}
jokuja
  • 89
  • 1
  • 15
  • This actually sounds very similar to [Minimum number of platforms for a railway station](https://stackoverflow.com/questions/62694219/minimum-number-of-platforms-required-for-a-railway-station) – Stef Aug 03 '21 at 14:33
  • i found sth even more similar but it would be much slower to iterate over all minutes: https://stackoverflow.com/questions/60288630/more-efficient-method-to-split-overlapped-intervals-then-merge-duplicates – jokuja Aug 03 '21 at 14:48
  • 1
    "iterate over all minutes"?? Why would you do that? Just iterate over the list of times in your data. – Stef Aug 03 '21 at 14:54
  • yes seems enough – jokuja Aug 03 '21 at 15:05

1 Answers1

-1

One way to do it is to create a sequence of "events" sorted in order of when they occur. An "event" is either a time when an id's range begins or a time when an id's range ends. Once you have the sorted list of events, you can process the events in order one at a time to produce the required output.

Mark Saving
  • 1,752
  • 7
  • 11