Click here to Skip to main content
15,609,550 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
I got this problem in a coding exam but unable to find the algorithm during the exam and find the solution online. Please help me solve it.

There are 'm' jobs which have to be completed by 'n' people. An nxm array will be given in which the value in the 'i' th row and 'j' th column represent the time taken by the 'i' th person to complete the 'j' th job. Any person can do any number of jobs. Find the least time to complete the jobs.
eg input:= n=5, m=4

nxm matrix= is:

5 5 5 5 
6 9 2 6
8 7 8 8
1 1 1 1
6 7 8 2

output:= 2

Explanation: The fourth person can do all jobs in unit time. The second person can do third job in a unit time, the fifth person can do fourth job in a unit time. So, as time starts, fourth guy will start doing first job, second guy the third job and the fifth guy the fourth job. After completing first, the fourth guy will complete second.

What I have tried:

I tried to solve but didn't get any idea.
Any algorithm which is better than brute-force?
Updated 1-Sep-20 21:41pm
KarstenK 1-Sep-20 12:58pm    
you have the side condition that every person needs to do a job while the others are working.

I think its ends with matrice to solve.

This is not a programming question. It's about finding an algorithm that gives you a correct result. Additionally it may be about finding an algorithm that gives you the result quickly, but you didn't say that. Either way, you might get more responses if you just remove the language tags.

The trick about finding (and evaluating) algorithms is finding *some* way that works, and then check whether it works in corner cases, or if there's something you can do to accelerate it, in case it's too slow.

The easiest approach to pretty much any problem with a limited number of potential solutions is called "brute force". Brute force means, you try every possible combination, and find out which one works.

In this case, the only problem is, what are the combinations, and how can I make sure I am trying them all? So let's look at the task: You have m jobs, and n people who could work on either of these jobs. That's a typical scheduling task. You can express this task as a list of assignments of jobs to people, e. g. {job 1, person 1}, {job 2, person3}, job 3, person 1}, {job 4, person 4}. Since every job is listed exactly once, and the order is not of importance, you can list this just as the list of persons instead, where the job number is implied by the position in the list. For the example above, that would be { 1, 3, 1, 4 }.

Going by that notation, if you want to express all schedules, you will need scheduling lists like this with the following conditions:
1. each list position corresponds to one of the m jobs, so the list has m elements.
2. each of the m elements corresponds to the number of one of the n people who will process the job at this position, so it can be any number from 1 through n

This means you need to set up a container for lists of m numbers, then generate all combinations of such lists by iterating each element from 1 to n, and add that combination to your container.

When you have that container, you have to find the best one, i. e. the one that results in the shortest processing time. For that you need a function that calculates the processing time for a given schedule. It shouldn't be hard to write that function.

For the example given, you'll get 5*5*5*5=625 schedules. For larger examples, the total number of schedules may be too large to store, so, instead of storing them in a container, you should just generate one schedule at a time, evaluate the processing time, and store that schedule only if it's among the best ones.

Moreover, for larger examples evaluating each and every schedule will be too time consuming: you should think of ways to reduce the number of schedules to test. But I won't delve into this here - for now it's only important for you to understand how to find 'a' solution, even if it's not the best one.
Share this answer
Rick York 1-Sep-20 14:10pm    
That's essentially how the program I work on operates. The problem does not have only one right answer so I have to try all of the possibilities and then determine which one was best. I am using a GPU to do it now.
Stefan_Lang 2-Sep-20 3:27am    
I once worked on a GA solving uch a scheduling problem. The example given had several hundred jobs and 4 machines - impossible to solve using brute force, and most certainly not in the 90s! But the GA could find a near optimal solution within 20 minutes, where a human expert (who formerly made that schedule) needed the better part of a week to arrive at a solution of similar quality.
Maciej Los 2-Sep-20 9:58am    
Stefan_Lang 2-Sep-20 11:46am    
Thanks a lot.
I tried to solve but didn't get any idea.

This is an indication that you are not skilled enough for the exam.
Because, as programmer, it is your job to analyze a requirement, and this 1 is not really complicated.
The keys are:
- A worker can do 0, 1 or more jobs.
- A job is done by exactly 1 worker.
- Minimize time to have all jobs completed.
Then take a sheet of paper and a pencil and start to solve by hand.
            Work time by worker
J0 J1 J2 J3 W0 W1 W2 W3 W4 Max time
W0 W0 W0 W0 20  0  0  0  0 20
W0 W0 W0 W1 15  6  0  0  0 15
W0 W0 W0 W2 15  0  8  0  0 15
W0 W0 W1 W1 10  8  0  0  0 10

This is basically a brute force algorithm (try every possibility)
Any algorithm which is better than brute-force?

For such a small dataset, not sure any other solution will be faster.
For this requirement, not sure any other algorithm exist.
Share this answer
KarstenK 2-Sep-20 2:32am    
sounds like linear algebra with 5 vectors (workers) and the side condition that all 5 are working. But I am not good in that ;-)
Patrice T 2-Sep-20 7:43am    
4 jobs and 5 workers, I doubt all will work.
I am using IP, but I don't see how to express the goal.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900