@Harish Your understanding is correct.
By reuse I meant that A(1) after being used in A(1)+ B(1) combination
can be reused in A(1)+B(2) if it fulfills the criteria.
Dave gave an algorithm that used A(1) once and did not include the
case where where A(1) can be used in any other combination.
On Oc
@amod
I am not sure I understand what you are saying.
It is assumed that the K smallest Items(from both list A & B) are identified
and arranged in increasing order as the first step.
Now A(1) and B(1) constitute "the least fare" round trip(since the list is
sorted) and we include that combination
@Algoose
Yes, but the algoritm is not correct since we are not covering the
condition where element is reused.
Ex ia=1 and ib=1
If we increment ia to 2 then there may be a case where A(1)+B(1) is
less than A(2)+B(1) but since 1 was denoted by ia which is now 2 hence
we will never be able to check t
@Dave I tried to run your algorithm but I am not getting the desired
results
Taking inputs as given by @coolfrog
AB
16
37
69
I am getting
AB Sum
167
369
66 12
96 15
and the desired output would have been
1 6 7
1
@Dave
input: k=3
AB
16
37
69
output should be (1,1,7), (1,2,8), (2,1,9)
im getting output form above code
(1,1,7)
(2,1,9)
(3,1,12)
Dave i am still learning algorithms .. so if i am wr
@Coolfrog$:
1. No. It should be O(n + k log k) because finding the kth smallest
element of an array of size n is O(n), using the Median of Medians
algorithm; see
http://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm.
2. Assuming that the e
@Dave
1. should it not be O(k + klogk) ??
2. but u are not considering all the possible values... let k =3
like i. a1+b1
ii. min( a1+b2, a2+b1) upto these fine one of them will be
chosen ...either ia or ib will increase.
iii. but know we have to take remaining
@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 a
@amod
as given A->B andB->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
@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
@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 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.
>
> Plea
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
Although no inputs are given on flight timing (date and time) front but that
is one more factor that should be considered while scheduling the cheapest
round trip journey as it happens on travel sites normally
On Wed, Oct 13, 2010 at 2:56 PM, Shiyam code_for_life <
mailshyamh...@gmail.com> 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
Could you please elaborate on O(n+m) algorithm that you have used
On Oct 12, 6:43 pm, ligerdave wrote:
> sorting is absolutely required. w/o the sorting, how are you going to
> find the min? comparison is also a sorting algorithm.
> it also depends on how many suggestions you wanna have. if it's
sorting is absolutely required. w/o the sorting, how are you going to
find the min? comparison is also a sorting algorithm.
it also depends on how many suggestions you wanna have. if it's just
the best deal, you can complete this in O(n+m) where n is the number
of different fares of trip to and m i
16 matches
Mail list logo
