I had 2 arrays (txs and interval) and I want the interval to includes txs which had a date between from and to (include).

const txs = [
   { price: 1, date: 1 },
   { price: 3, date: 2 },
   { price: 1.7, date: 4 }
];

const interval = [
   { from: 1, to: 2, txs: [] },
   { from: 2, to: 3, txs: [] },
   { from: 3, to: 4, txs: [] }
];

expected result

[
   { from: 1, to: 2, txs: [{ price: 1 }, { price: 3 }] },
   { from: 2, to: 3, txs: [{ price: 3 }] },
   { from: 3, to: 4, txs: [{ price: 1.7 }] }
]

And this is my solution in O(n^2)

for (let i of interval) {
  for (let j of txs) {
     if (j.date >= i.from && j.date <= i.to) {
        i.txs.push({ price: j.price });
     }
  }
}

this is only an example. the real one txs and interval could have more than 10,000 elements. is there any solution that can be done in O(n) or O(n log n) ?

CodePudding user response：

Let me call the length of txs n and that of intervals m. Following cucaracho's hint, you have one O(n log(n)) precomputation. Finding the first "txs" to include (if any) takes O(log n) for each interval. Adding one txs should take O(1) for a total of O(n log(n) m log(n)  mn) = O((n   m) log(n)  mn).
To get that annoying term mn ("size of output") out of the picture, find the first txs not to include and for each interval represent the txss to include by specifying this one in addition to the first.

For non-overlapping intervals, just ordering both arrays and walking both may be faster, one influence being relative array size.