alternative to sort algorithm less than O(nlog(n))

Question

I have recieve as input a list of candidates for work so that the list I recieve is already sorted by requirments of the salary for each one and also is grase from the university(this parameter is not sorted). example:

danny 13000$ 75.56

dan 9000$ 100

bob 5000$ 98

in such a list I need to find the two candidates with the higher grades so that sum of both salary is not more than 10000$ (I can assume their is no two candidates with the same grade and there are no two pair of students with the same sum of grade (94+90 = 91 + 93))

I need to find them in comlexity of O(n).

I understand I can not do a sort algorithm (the min is n*log(n)) so How can I do that ?

is it possible ?

Note that it is a private case (much simpler) of knapsack problem, with only 2 elements to chose. — amit
– amit, Commented Dec 27, 2012 at 11:15

amit · Accepted Answer · 2012-12-27 11:31:40Z

O(n) solution (assuming the number 10,000 is fixed):

arr <- new empty array of size 10000
for each i from 1 to 10000:
   arr[i] = "most valuable" worker with salary up to i
best <- -infinity
for each i from 1 to 5000:
   best = max{ best, arr[i] + arr[10000-i]}
return best

The idea is to hold an array where in each entry you hold the "best" candidate that asked for at most that salary (this is done in the first loop).

In the second loop, you go over all feasible possibilities and finds the max.

Note that the naive approach for the first loop is O(n) with terrible constants (each iteration is O(n), and it is done 10,000 times). However, you could build arr using DP by going from the lowest salary up, and doing something like:

arr[i] = max {arr[i-1], best worker with salary i}

The DP solution is O(n) with only once traversal over the array (or formally O(W+n) where W is the max salary).

Also note - this is a private case of knapsack problem, with the ability to choose only 2 elements.

Rusty Rob · Accepted Answer · 2012-12-27 19:41:26Z

1

since it is sorted by salary start with two pointers. i pointing to the start (lowest salery) and j pointing to the highest salery. now while the salery is over the limit decrease j. now increase i and decrease j staying below the limit. track the maximum grade for i and for j.

edited Dec 27, 2012 at 19:41

answered Dec 27, 2012 at 11:30

Rusty Rob

17.3k10 gold badges103 silver badges121 bronze badges

2 Comments

Patricia Shanahan Over a year ago

It is not sorted by grade, but by salary.

Rusty Rob Over a year ago

sorry i meant to say salary

Collectives™ on Stack Overflow

alternative to sort algorithm less than O(nlog(n))

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related