Rephrase the problem as follows:

Given are foods \(R_1, R_2, \dots, R_H\) and drinks \(C_1, C_2, \dots, C_W\).

Each of \(N\) people has a preference of foods and drinks. The preference of person \(i \, (1 \leq i \leq N)\) is:

• The person wants one of \(R_{a_i}, R_{a_i + 1}, \dots, R_{c_i}\), and one of \(C_{b_i}, C_{b_i + 1}, \dots, C_{d_i}\).

Supposing that the same drink or food cannot be assigned to multiple people, what is the maximum number of people whose preferences are satisfied?

This can be boiled down to a maximum flow problem.

• Prepare the following vertex.
  • \(\mathrm{src}, \mathrm{dst}\)
  • \(R_1, \dots, R_H\)
  • \(C_1, \dots, C_W\)
  • \(U_1, \dots, U_N\)
  • \(V_1, \dots, V_N\)
• Add an edge with capacity \(1\) from \(\mathrm{src}\) to every \(R_i\).
• For each \(i \, (1 \leq i \leq N)\),
  • add an edge with capacity \(1\) from \(R_{a_i}, R_{a_i + 1}, \dots, R_{c_i}\) to \(U_i\).
  • add an edge with capacity \(1\) from \(U_i\) to \(V_i\).
  • add an edge with capacity \(1\) from \(V_i\) to \(C_{b_i}, C_{b_i + 1}, \dots, C_{d_i}\).
• Add an edge with capacity \(1\) from every \(C_i\) to \(\mathrm{dst}\).
• Compute the maximum flow from \(\mathrm{src}\) to \(\mathrm{dst}\).

The graph corresponding to the Sample Input 1 is shown below.

If we use the Ford-Fulkerson algorithm, it can be solved in a total of \(O(FE)\) time; if Dinic’s algorithm is used, it can be solved in a total of \(O(E\sqrt V)\), where \(V = H + W + N, E = (H + W)N, F = \min(H, W, N)\).

Sample code (C++)