Selecting optimal order of questions to minimize total time

Question

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be the set of questions that a student has a doubt it. Assume that $\forall 1 \leq j \leq n: Q_j \neq \phi$ and $\bigcup_{1\leq j\leq n}Q_j = Q$.

Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the time spent by $s_j$ in the tutorial session. We want to find out an optimal permutation $\sigma$ in which questions are discussed $(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $\Sigma_{1\leq j \leq n}t_j$ is minimized.

Intuitively it seems that we can greedily discuss the question that the most number of students (in the current iteration) have a doubt in. Is the greedy algorithm correct?

Sidenote: By the way, I thought of this question after an actual tutorial session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!

Answer 1

Counterexample: Students are $x_1\dots x_n$ and $y_1\dots y_m$ and questions are $Q_0, \dots Q_m$. Students $x_i$ only want $Q_0$ to be answered while the $y_i$ students want question $Q_1,\dots, Q_m$ to be answered.

Let's say you place $Q_0$ as the $k^{th}$ question. Then the total time waited by students is:

• $L(n,m)=n(m+1)+m^2$ if $Q_0$ is last

• $nk + m(m+1)$ if $Q_0$ is $k^{th}$

Clearly, if you want to not put $Q_0$ last, then you might as well put it first so that the cost is $F(n,m)=n + m(m+1)$.

Now $L(n,m)-F(n,m)=nm+n+mm-n-mm-m=nm-m=(n-1)m$ so that whenever $n>1$ and $m>0$, we'll have $L(n,m)>F(n,m)$. So placing it first is better.

But your greedy algorithm would put it last if we take $m>n$.