Java – Select M projects from N projects so that the tasks for those M projects take the least amount of time to complete

I’m trying to fix the following:
Give you N elements. Each item contains three tasks A, B, and C, and the time required to complete task A is TA, task B is TB, and task C is TC. Now we must select M projects so that the tasks of these M projects take the least amount of time to complete. The rules are as follows:

Operate all selected M items at the same time, that
1. is, tasks that operate all M items at the same time

Task

2. B cannot start any of the selected items unless Task A completes for all M items

Task

3. C for any of the selected items cannot be started unless Task B for all M items is complete

For example:

if say N = 3 and M = 2 (it means we must select M items out of 3 items in total)
         Tasks: A  B  C
       item 1 : 1  2  2
       item 2 : 3  4  1
       item 3 : 3  1  2

If we select Project 1 and Project 3, Task A of both projects completes after 3 units

(Project 1 waits for Project 3 to complete), and then Task B of both projects completes after the next 2 units of time. Similarly, Task C completes after 2 units of time. So the total time is 7 (which is the smallest possible combination we can find).

I tried to come up with a dynamic programming solution to solve this problem. But I can’t get a concrete solution to the problem. Can anyone help me by providing effective solutions to the problem.

PS: Please don’t write code. I’m just looking for logic here.

Thank you in advance.

Greedy method solution (weight calculation + cutoff time sorting).

Here’s a greedy way to solve this problem, I hope it helps you. Good luck!

Since each task in a project takes time t to complete, we can think of these as “deadlines” for these tasks (A, B, and C). We can visualize these deadlines as if they were “slots” in an array/sequence of slots.

To visualize these deadlines, consider these examples;

Task A of item 2;

0__A__1__A__2__A__3

Task C of item 1;

0__C__1__C__2

Now let’s think about it; We have K “slots” in our hands 0__1__2__ … __K, the problem requires us to spend the least amount of slots possible.

Another example you explained is to better visualize the problem, our slot takes this form when you select item1 and item3;

item1 + item3 “deadline slot occupation”

0_A_1_A_2_A_3_B_4_B_5_C_6_C_7

Because task A of item3 costs 3 more units than item1, the first three slots are occupied. Task B can only start after this “longer” task A is completed, so start at slot number 3.

So the problem becomes; Fill our slots with the minimum number of slots spent. Therefore, we will take a greedy approach to this issue.

• Find a separate “deadline period” for M projects that we want to select from N

In the example you provided;

For item1;

0_A_1_B_2_B_3_C_4_C_5

5 locations occupied

For item2;
8 slots are occupied

For item3;
6 slots are occupied

For itemX;
P slot is occupied, etc….

After knowing the number of slots each project needs in task time
We will check the M subtraction as a portfolio in N project tasks to get the smallest possible amount.

Example;
Select M term when M=2;

Item1-Item2 = 5;

Item1-Item3 = 3;

Item2-Item3 = 4;

**Edit; Item1 – Item2 corresponds to the absolute value of subtraction in the selected number of items combination; For example, if M=2; |a1-a2| + |b1-b2| + |c1-c2| …

So for M=2 choices, we take the smallest result 3, which leads us to choose Item1 and Item3 as the solution.

This number will give us the minimum number of slots used. So, this leads us to a solution.