Trusted answers to developer questions

Izza Mujeeb

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Let’s consider five processors and seven tasks. A processor can only run one task at a time, and a task can only be selected by a single processor. For example,

Now, what if we wanted to ensure efficiency by matching the maximum number of tasks to the maximum number of processors? This is one of the maximum bipartite matching problems, the need to match as many entities as possible, and this is where bipartite matching comes into play.

A graph ** **vertices of the same sets are not to be connected, and edges can only exist between the vertices of

Click here to learn about bipartite graphs.

**Bipartite matching** is the opting of edges in such a way that there will be no adjacent edges—no same set edges (between

In the above scenario, obtaining the maximum number of tasks that can be run on corresponding processors is the solution to our problem, but how do we do that exactly?

Such a problem can be solved very effectively by the** Ford Fulkerson algorithm, **which connects and disconnects all possible edges in the graph till the maximum match number is found, such as the highest edge count.

#include <iostream>#include <string.h>using namespace std;// this function recursively uses the DFS approach to find out the most optimal combination// of edge connections by adding and removing edges one by onebool isMatchingPossible(bool graph[7][5], int task, bool visited[], int assigned[]) {for (int processor = 0; processor < 5; processor++) {if (graph[task][processor] && visited[processor] != true) {visited[processor] = true;if (assigned[processor] == -99 || isMatchingPossible(graph, assigned[processor], visited, assigned)) {assigned[processor] = task;return true;}}}return false;}// this function returns the maximum number of matches that can be made in a bipartite graphint maximumMatching(bool graph[7][5]) {int assigned[5], totalProcessorsAssigned = 0;bool visited[5];for (int processor = 0; processor < 5; processor++)assigned[processor] = -99;for (int task = 0; task < 7; task++) {for (int processor = 0; processor < 5; processor++)visited[processor] = false;if (isMatchingPossible(graph, task, visited, assigned) == true)totalProcessorsAssigned++;}return totalProcessorsAssigned;}// main codeint main(){bool graph[7][5] = { {1, 0, 0, 0, 0},{1, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1} };cout << "The processors can run a maximum of "<< maximumMatching(graph) <<" tasks at one time." << endl;return 0;}

Maximum bipartite matching of processors and tasks

In the above code, we use `maximumMatching`

, which takes `graph[7][5]`

that contains 7 tasks and 5 processors** **that run `isMatchingPossible`

- Line 13: We use
`if (graph[task][processor] && visited[processor] != true)`

to find an unvisited processor and mark it visited for the task passed through the function. - Line 17: The
`assigned[processor] == -99`

is`true`

when the processor is not allocated. Otherwise, we call`isMatchingPossible`

recursively to find another processor. - Line 19: We use
`assigned[processor] = task`

, which assigns the task to the unassigned processor. - Line 32: We use
`int assigned[5]`

to define an integer array to keep a track of which task will be assigned to which processor during the matching. - Line 34: We use
`bool visited[5]`

to define a boolean array to keep a record of the processors visited during traversal to avoid cycles. - Line 44: The
`isMatchingPossible`

keyword performs the DFS traversal for each task to find a possible match.

- Jobs are assigned to a maximum number of people who are interested in specific jobs.
- One crucial case in point would be effectively matching available kidney donors to kidney transplant recipients.

O(mn): Where m denotes the number of edges, while n denotes vertex count.

RELATED TAGS

graph

CONTRIBUTOR

Izza Mujeeb

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses