@Coolfrog$: You don't have to sort the arrays. You only have to find
the k smallest elements in each and sort those k entries. This can be
done in O(n + k log k).
Algorithm:
find the smallest k elements of A and sort them into ascending order.
find the smallest k elements of B and sort them into ascending order.
ia = 1
ib = 1
output ia, ib, A(ia)+B(ib)
for n = 1 to k do
if A(ia + 1) + B(ib) > A(ia) + B(ib + 1) then
ia = ia + 1
else
ib = ib + 1
end if
output ia, ib, A(ia)+B(ib)
end for
Complexity O(n + k log k).
Dave
On Oct 15, 4:00 am, "coolfrog$" <[email protected]>
wrote:
> @amod
> as given A->B and B->A are in sorted form...if not sort them in
> O(n log n).
> then
> first suggestion A1+B1
> second suggestion MIN( A1+B2 , B1+A2) ===> let it be B1+A2
> third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2)====> let it be
> A2+B3
> and so on...
>
> @Dave what will be complexity of above solution...?
> i think O(n log n) for sorting and second part (suggestions) O(n)..
>
> Guys do correct me plz...
>
>
>
>
>
> On Thu, Oct 14, 2010 at 11:10 AM, Amod <[email protected]> wrote:
> > @Dave You are partly correct.
>
> > If i ask for four minimum fares for the round trip then
> > first suggestion is what u said : sum the sum of the minimum cost from
> > A to B and the minimum cost from B to A
> > after that we have to see which combination from both costs, sums up
> > least
>
> > On Oct 14, 9:55 am, Dave <[email protected]> wrote:
> > > @Amod. Isn't the minimum sum the sum of the minimum cost from A to B
> > > and the minimum cost from B to A? What am I missing?
>
> > > Dave
>
> > > On Oct 13, 11:06 pm, Amod <[email protected]> wrote:
>
> > > > Hi
>
> > > > I think I forgot to mention that the SUM of the ROUND trip i.e. A->B->A
> > (sum = going + returning) should be least.
>
> > > > Please don't take into account any other thing like time and
> > > > availability.
> > > > So solution is not that straightforward.
>
> > > > Its like we have two arrays and we have to return least k sum from the
> > > > given arrays where we take one element from the first and one from
> > > > second in the sum.
>
> > > > Cheers
> > > > Amod
>
> > > > On Oct 13, 2:26 pm, Shiyam code_for_life <[email protected]>
> > > > wrote:
>
> > > > > When a user wants to choose to fly from A to B, suggest the flight
> > > > > with lowest fare that's available, here its A1, if A1 is busy then A2
> > > > > and so on
> > > > > Repeat the same for B to A.
>
> > > > > Am I missing something here?
>
> > > > > Complexity is O( (number of flights from A to B) + number of flights
> > > > > from B to A) )
>
> > > > > Cheers
>
> > > > > 'Coding is an art'- Hide quoted text -
>
> > > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> *Divesh*
> (¨`·.·´¨) Always
> `·.¸(¨`·.·´¨ ) Keep
> (¨`·.·´¨)¸.·´Smiling!
> `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
> of reasons 2Smile"- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
