Break array of objects into 2dimensional array

Question

I need to break an array of objects into a 2-dimensional array where 1-dimensional arrays would consist of objects which have their attributes 'for' and 'to' being not overlapping intervals.

Example: Given array arr1 I wish to receive arr2

const arr1 = [
  {
    from: 0,
    to: 2,
  },
  {
    from: 0,
    to: 6,
  },
  {
    from: 3,
    to: 7,
  },
  {
    from: 2,
    to: 4,
  },
]

arr2 = [
  [
    {
      from: 0,
      to: 2,
    },
    {
      from: 3,
      to: 7,
    }
  ],
  [
    {
      from: 0,
      to: 6,
    }
  ],
  [
     {
       from: 2,
       to: 4,
     }
  ],
]

How it should work: We loop through the arr1. Object1 should be put into the first 1-dimensional array in arr2 by default.

Object2 overlaps with Object1 so it should be put into a separate array in arr2.

Object3 does not overlap Object1 so it should be put into the first 1-dimensional array with Object1

Object4 overlaps with Object1 so it should be put into the second 1-dimensional array to Object3, but it also overlaps with Object3 so it should be put into a separate 1-dimensional array.

I need to find the solution with as less loops as possible)

user_1447675 · Answer

You could iterate the result array and find a slot if all items do not overlap.

const
    array = [{ from: 0, to: 2 }, { from: 0, to: 6 }, { from: 3, to: 7 }, { from: 2, to: 4 }],
    result = array.reduce((r, o) => {
        if (!r) return [[o]];
        const group = r.find(a => a.every(({ from, to }) => o.to <= from || to <= o.from));
        if (group) group.push(o);
        else r.push([o]);
        return r;
    }, undefined);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

user_10914270 · Answer

This is known as the Interval partitioning problem

Here is an implementation of the greedy algorithm:

var arr1 = [
  {
    from: 0,
    to: 2,
  },
  {
    from: 0,
    to: 6,
  },
  {
    from: 3,
    to: 7,
  },
  {
    from: 2,
    to: 4,
  },
];

function partitionIntervals(data){
  var copy = [...data];
  copy.sort((a, b) => a.from - b.from);
  var res = [];
  outer: for(var x of copy){
    for(var slot of res){ // add to the first open slot
      if(slot[slot.length - 1].to <= x.from){
        slot.push(x);
        continue outer;
      }
    }
    res.push([x]); // else create a new slot
  }
  return res;
}

arr2 = partitionIntervals(arr1);
console.log(arr2)

Break array of objects into 2dimensional array

2 Answers