0
$\begingroup$

Say I have two arrays, { energy and score }, and they could have elements like this:

E: 1  3  4 7
S: 16 10 5 1

What I want is the best score with the best energy. What data structure can support inserting items in a way that I don't have have an item with less energy and less score than another item i.e. for any i,j where i!=j => score[i] > score[j] || energy[i] > energy[j]

When inserting, I do three steps:
1- if any item has more or equal score and energy, return;
2- if any item has less or equal score and energy, remove this item;
3- insert the required item.

Here are some examples:

1- insert e=8, s=1. The arrays become:

E: 1  3  4 8
S: 16 10 5 1
           ^

2- insert e=5, s=6. The arrays becomes:

E: 1  3  5 8
S: 16 10 6 1
         ^

3- insert e=5, s=11. The arrays becomes :

E: 1  5  8
S: 16 11 1
      ^    (3,10) is removed because (5,11) has more energy and more score than it.

What data structure can support this in (hopefully) O(logn) time?

$\endgroup$
2

0

Browse other questions tagged or ask your own question.