Hi! Interesting... but I still don't grasp the terminology.
What is a "round trip recommendation"? Why outbound flights are numbers and inbound flights are letters? Where are the "airports"? What is the criteria for grouping? Angel "Java" Lopez @ajlopez On Wed, Jul 17, 2013 at 9:10 AM, Andres Duque <[email protected]> wrote: > Hi all, > > I have this real life problem, maybe someone could find a better/easier > solution than mine :-). I need to optimize and generalize the solution. > This process will be executed +1M times each day, therefore, any > millisecond saved will be useful. > > PROBLEM > You have round trip recommendations (at this time I'm simplifying it only > to two points but the problem must be generalized to several points): > > N Outbound Inbound > 1 1 A > 2 1 B > 3 1 C > 4 2 A > 5 2 C > 6 2 D > 7 3 D > > The goal is to build groups of combinable Inbound/Outbound flights > maximizing the group sizes a minimizing the number of groups (both are > related). > > For the example we could build 3 optimal groups: > > 1st Group (4 possible combinations) > Outbound flights: 1, 2 > Inbound flights: A, C > > 2nd Group (2 possible combinations) > Outbound flights: 2, 3 > Inbound flights: D > > 3rd Group (1 possible combinations) > Outbound flights: 1 > Inbound flights: B > > As you can see, there are several possible solutions but it maximize the > groups size: 4, 2, 1 (possible combinations) and minimize the number of > groups: 3. > > Note the original problem must consider several points (not limited to > round trip). > > I tried with: > > * A greedy algorithm but it doesn't find biggest groups in some scenarios. > * A LCS algorithm adaptation but I could find a suitable one ( > http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) > > Now I have a heuristic solution but maybe its not the best/easier approach > and it's hard to extend it to several points. > > INITIAL SOLUTION > Build a matrix with the recommendations: > > A B C D > 1 X X X > 2 X X X > 3 X > > Later sort this matrix by columns and later by rows in desc order, think X > like bit '1' and no connection like '0' where left-most, top-most is higher. > > After sort by columns: > > A C B D > 1 1 1 1 0 > 2 1 1 0 1 > 3 0 0 0 1 > > After sort by rows (no changes): > > A C B D > 1 1 1 1 0 > 2 1 1 0 1 > 3 0 0 0 1 > > Now we find biggest rectangles of 1's using an optimal algorithm (maybe > precalculating 1's at right of each cell. With it, we can identify the 3 > groups: > > 1st group: 1, 2 --> A, C > 2nd group: 2, 3 --> D > 3rd group: 1 --> B > > Note above is better solution than: > > 1st group: 1 --> A, C, B > 2nd group: 2 --> A, C > 3rd group: 2, 3 --> D > > because with the 1st one we have a group of 4 recommendations (bigger than > 3 recommendations for the 2nd solution). > > Any idea is welcome. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/94ccbb62-7829-4cd2-a803-c5a042e84db6%40googlegroups.com > . > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMs%2BDqJX53sAzOXybjhRUDtNa6o4QPxKOz1qbwdtQubkLHGwYQ%40mail.gmail.com. For more options, visit https://groups.google.com/groups/opt_out.
