CODEWITHSUNDEEP
javascriptnode.jsdatemomentjs
haemse
haemse

Reputation: 4263

Merge sets of overlapping time periods into new one

Whats a nice and efficient way in node.js to merge several sets of given time periods into one set that represents the overlap time periods? Periods are provided as starting day and ending day.

4 sets of time intervals (days):

 (-------------------------)         (---------)                (---)
                       (------------------------)           (-------)
                 (--------)            (-------)                (----)
       (---------------------)     (---------)     (---)      (-----------)

New set representing overlaps:

                       (--)            (-----)                  (---)

Upvotes: 0

Views: 492

Answers (1)

Bergi
Bergi

Reputation: 664206

Merge all begin and end timestamps into a single list (storing timestamp and whether it's begin or end) - either naively or using a more efficient algorithm if you have a lot of sets.

  (-------------------------)         (---------)                (---)
                        (------------------------)           (-------)
                  (--------)            (-------)                (----)
        (---------------------)     (---------)     (---)      (-----------)


  (     (         (     (  )) )     ( ( (     ))))  (   )    ( (((   )))   )

Then use a simple increment/decrement scan over time:

0 -                                              ----   ------             ---
1 (------                     -------           -)  (---)    (--      -----)
2       (----------         --)     (--         )              (-    -)
3                 (------  -)         (--     --)                (   )
4                       (--)            (-----)                  (---)

And collect those intervals where the count is the maximum.

                        ^^^^^           ^^^^^^^                  ^^^^^

Upvotes: 3

Related Questions