How can i solve this problem(related to algorithms)?

Question

PROBLEM You are running a physics experiment with n complicated steps that you must do in order, and students sign-up for some steps to help. Your experiment requires n steps, and each of the m students gives you a list of which steps they can help out with (steps require special skills). From experience, you know things run most smoothly when you have as little switching of shifts as possible.

For example, if your experiment has <1, 2, 3, 4, 5, 6> steps

Student 1: <1, 2, 3, 5>

Student 2: <2, 3, 4>

Student 3: <1, 4, 5, 6>

Your optimal solution would be:

-- > Student 1 <1, 2, 3>, Student 2 does no steps, Student 3 does <4, 5, 6>. Only 1 switch

Another example if your experiment has 8 steps <1, 2, 3, 4, 5, 6, 7, 8>

Student 1: <5, 7, 8>

Student 2: <2, 3, 4, 5, 6>

Student 3: <1, 5, 7, 8>

Student 4: <1, 3, 4, 8>

Your optimal solutions could be any one of these:

-- > Student 1 does no steps, Student 2 does <2, 3, 4, 5, 6>, Student 3 does <1,7, 8>, Student 4 does no steps .2 switches (student 3 does step 1, student 2 does up to 6, student 3 picks up again to do 7 and 8)

-- > Student 1 does <7, 8>, Student 2 does <2, 3, 4, 5, 6>, Student 3 does <1>,Student 4 does nothing. 2 switches

-- > Student 1 does no steps, Student 2 does <2, 3, 4, 5, 6>, Student 3 does <7,8>, Student 4 does <1>. 2 switches

Given: n number of steps, m number of students that give you a list of steps (sorted) they can participate in. Assume there's a lookup table where you can find if student X signed up for step Y in O(1), so no need to factor that into your runtime.

Find: An optimal way to schedule students to steps such that there is the least amount of switching as possible.

Answer 1

The present algorithm in python chooses an optimal switching sequence.

The output gives the sequence showing at each step, the sub-list and also the min and max elements in each selected sub-list

sets=[[1,2,3,5],[2,3,4],[1,4,5,6]]
sets=[[5,7,8],[1,3,4,8],[1,5,7,8],[2,3,4,5,6]]
sets=[[5,7,8],[1,3,4,8],[1,5,7,8],[2,3,4,5,6],[2,3,4,5,8],[1,3,7,9,10]]
n = len(sets)

def findlongest(lista,k):
    j = k
    while j in lista:
        j += 1
    return j-1

maxn = 0
for i in range(n):
    maxn = max(maxn,max(sets[i]))

i    = 1
path = []
k    = 0
VOID = -1


while i <= maxn:
    kmax = 0
    j0   = 0
    for j in range(n):
        if i in sets[j]:
            k = findlongest(sets[j],i)
            if k > kmax:
                kmax = k
                j0   = j
    if j0 != VOID:
        path.append([j0+1,[i,kmax]])
        i = kmax+1

for i in range(len(path)):
    print(path[i])

For the sets

sets=[[5,7,8],[1,3,4,8],[1,5,7,8],[2,3,4,5,6],[2,3,4,5,8],[1,3,7,9,10]]

the algorithm gives the result

[2, [1, 1]]
[4, [2, 6]]
[1, [7, 8]]
[6, [9, 10]]

Answer 2

If a student is doing step $a$ and is qualified for all the steps $a, a+1, \dots, b-1, b$, there is no reason to switch away from the student at any time before step $b$. So we can assume that once a student starts doing a step, they keep working until they reach a step they're not qualified to do.

Let $[0], [1], \dots, [n]$ denote the possible states we can be in: state $[k]$ denotes that the first $k$ steps have been completed. A student qualified to do steps $a$ through $b$ but not $b+1$ can get us from state $[a-1]$ to state $[b]$, or from any of the states $[a], [a+1], \dots, [b-1]$ to state $[b]$ without switches, after which we need to switch to another student.

We can represent this as a graph with vertex set $[0], [1], \dots, [n]$. If a student is qualified to do steps $a$ through $b$ but not $b+1$, we represent that as directed edges $[a-1] \to [b], [a] \to [b], \dots, [b-1] \to [b]$. (We can label those edges with the student's name to remember who is doing what.) For example, a student qualified to do steps $1, 2, 3, 5$ gives us the edges $[0] \to [3]$, $[1] \to [3]$, $[2] \to [3]$, and $[4] \to [5]$.

Now to get all steps done in the minimal number of switches, we can just find a shortest path from $[0]$ to $[n]$ in this graph. The number of switches is one less than the number of edges in the path.

For instance, in your second example, a shortest path is $[0] \to [1]$ (using student $3$ or $4$) then $[1] \to [6]$ (using student $2$) then $[6] \to [8]$ (using student $1$ or $3$), which gives us a solution with $2$ switches.