Since the priority queue operation delete min must be O(log n) the
running time here can't be better than O(n log n).
On Oct 16, 11:06 am, "juver++" <avpostni...@gmail.com> wrote:
> Keep priority queue of pairs - sum and respective indices in the
> arrays.
> Start from pair (a[0] + b[0], (0, 0)).
>
> while (queue is not empty && n > 0) {
> retrieve largest sum from the queue, (sum, (i, j))
> add sum to the result array
> --n;
>
> add pairs (a[i + 1] + b[j], (i + 1, j)) and (a[i] + b[j + 1], (i, j
> + 1)) if it is possible due the boundings;
>
> }
>
> The additional care should be taken to avoid processing pair of
> indices twice.
>
> On 14 ÏËÔ, 11:55, Harshal <hc4...@gmail.com> wrote:
>
>
>
> > Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's
> > say they are decreasingly sorted), we define a set S = {(a,b) | a \in A
> > and b \in B}. Obviously there are n^2 elements in S. The value of such
> > a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
> > from S with largest values. The tricky part is that we need an O(n)
> > algorithm.
>
> > --
> > Harshal Choudhary,
> > III Year B.Tech Undergraduate,
> > Computer Engineering Department,
> > National Institute of Technology Surathkal, Karnataka
> > India.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
