CareerCup

its 11

Well, if only 1 person can pass each time, it will take 21 minutes, but 2 people can cross the bridge at the same time, so the minimum optimal time is 10.5 (assume that the bridge has 2 people crossing at any given time, which is impossible if t is not integer), and we can tell that the optimal solution is integer.

11 works, (7 & 10 go, 3 go when 7 reach the other side, at t = 10, 1 go across // one side 3 & 7 & 1, the other 10). Thus, 11 is the optimal solution.

Is it 11 min?

3+7=10 & 10 means all will cross in 10 mnts ...
Last one can cross in one mnts hence ... 10+1=11 is optimal...

// We can make this problem more general.
// Consider more than 4 men, for example, a set {15, 14, 10, 7, 5}
// We can find that the mininum time is such a division that two subsets has a mininum difference.
// e.g subset1 = {15,10}, subset2 = {14,7,5};
// Ideally, the min time should be perfect match, pm = SumOfSet/2;
// If there is such a match, we find the answer, otherwise pm++;
// It can be solved recursively.
// C++ code:

#include <iostream>
#include <new>

using namespace std;

bool FindSubsetSumTo( int pm, int array[], int N, bool visited[] );

int MinCrossBridgeTime( int array[], int N );

int main( int argc, char* argv[] )
{
    int a[] = {1, 3, 7, 10};
    int b[] = {15, 14, 10, 7, 5};
    int c[] = {2994, 1443, 533, 2324, 1133, 4444, 2382};

    cout << "minimum time: " << MinCrossBridgeTime( a, 4 ) << endl << endl;
    cout << "minimum time: " << MinCrossBridgeTime( b, 5 ) << endl << endl;
    cout << "minimum time: " << MinCrossBridgeTime( c, 7 ) << endl << endl;

    return 0;
}

int MinCrossBridgeTime( int array[], int N )
{
    int pm = 0;
    for( int i = 0; i < N; i++ ) pm += array[i];
    if( pm %2 == 1 ) pm = pm/2 +1;
    else pm /= 2;
    bool* used = new bool[N];
    bool found = false;
    while( !found )
    {
        for( int i = 0; i < N; i++ ) used[i] = false;
        found = FindSubsetSumTo( pm, array, N, used );
        if( found )
        {
            cout << "subset1: ";
            for( int i = 0; i < N; i++ )
                if( used[i] ) cout << array[i] << " ";
            cout << endl;
            cout << "subset2: ";
            for( int i = 0; i < N; i++ )
                if( !used[i] ) cout << array[i] << " ";
            cout << endl;
            return pm;
        }
        else pm++;
    }
}

bool FindSubsetSumTo( int pm, int array[], int N, bool used[] )
{
    if( pm == 0 ) return true;
    if( pm < 0 ) return false;
    bool found = false;
    int i = 0;
    while( !found && i < N )
    {
        if( !used[i] )
        {
            used[i] = true;
            found = FindSubsetSumTo( pm-array[i], array, N, used );
            if( !found ) used[i] = false;
        }
        i++;
    }
    return found;
}

The result is:

subset1: 1 3 7 
subset2: 10 
minimum time: 11

subset1: 14 7 5 
subset2: 15 10 
minimum time: 26

subset1: 2994 2324 2382 
subset2: 1443 533 1133 4444 
minimum time: 7700

@DashDash :Min value would be 20 min,here you have to think logic so that 2 max time taking person walks together on the bridge and should not repeat walking to the bridge again back and forth.
I think now you get easily find the solution on your own ;)

10 minutes.

Let 10 start in lane 1, and 7 start in lane 2. After 7 minutes, let 3 start in lane 2. After 9 minutes, let 1 start in lane 1.

Even I think it's 11 mins is optimal

Even I think it's 11 mins is optimal

11 is Ofcourse an Answer but I think the question is something different.. I have seen somewhat like this is a greater difficulty.

Yes its 11

It is 11.

Its 11
This is very simple :)

Can some one explain how it is 11 min? 1. 10 & 7 starts, When 7 is finishes 3 starts ..10 and 3 finish at the same time ...1 is still left..he can not walk alone..

11 minutes:
1=10 minutes
2=3+7+1 minutes

The answer is 17 Mins.

At a given time only 2 people can cross the bridge. SO the optimal way is ,

1,2,7,10 ---------> 1,2 2 mins
1,7,10 <---------2 1 mins
1 --------> 2,7,10 10 mis
1,2 < --------,7,10 2 mins
----------> 1,2,7,10 2 mins

Total = 2+1+10+2+2 = 17mins

first 7 min : from lane1 10 and lane2 :7
next 3 min : from lane1 10(cont.) lane2 3(join)
last 1 min : from lane 1 1

hence 11 is optimal solution

first 10,1 ->1minute
next 10-1,3 ->3 minute
next 10-1-3,7 -> 7minutes

Its 20 Minutes.
1,3,7,10
First : 7,10 l--------l 1,3 = 3 mins
1,7,10 l--------l 3 =3+1=4
2nd 1 l--------l 3,7,10=4+10
1,3 l--------l 7,10 = 14+3
3rd l--------l 1,3,7,10 =17+3

which is 20 minutes . Any doubts