5: Suppose that there are p companies and that the ith company sends m represent

Question

5: Suppose that there are p companies and that the ith company sends m representative to a conference. In this conference, there will be q work groups, each with at most n, participants. The organizers of the conference want a schedule that assigns each representative to exactly one group, but no group can contain two representatives from the same company. The groups do not have to be filled to capacity. Show how to use network flows to test whether the constraints can be satisfied. For this problem, you have to describe the network and how it can be used to test whether the constraints can be satisfied.

Explanation / Answer

We can solve this problem following ways .

Firstly Short all Company by presentative strength and groups by capacity.(That will help us to disallowed duplicate representative in perticular group)

Step 1-> We will go by Company by company whose representative strength is less

Step 2-> Then Select One representative of the company

Step 3 -> Put that representative into one of the group(Whose grop capacity is higher)

Step 4-> Decrease group capacity by one ,That means its occupied by one of the company reprenstative.

Step 4 -> Repeat same process.

Java Code is for the same is following

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

import java.util.stream.IntStream;

public class CompanyGroupScheduler {

public static void main(String arg[]){

Scanner sc=new Scanner(System.in);

System.out.println("Enter Number of Company :" );

int noCompanies=sc.nextInt();

int reprensative[]=new int[noCompanies];

for(int i=0;i<noCompanies;i++){

System.out.println("Enter number of Representative for company "+(i+1) +" :");

reprensative[i]=sc.nextInt();

}

System.out.println("Enter number of Groups :");

int groups=sc.nextInt();

int groupCapacity[]=new int[groups];

for(int i=0;i<groups;i++){

System.out.println("Enter Capacity for Group "+(i+1) +" :");

groupCapacity[i]=sc.nextInt();

}

//Short Company by representative

Arrays.sort(reprensative);

//Short Groups by capacity

int[] groupCapacitysorted = IntStream.of(groupCapacity)

.boxed()

.sorted(Comparator.reverseOrder())

.mapToInt(i -> i)

.toArray();

//Moveing for each company

for(int i=0;i<reprensative.length;i++){

//Moving for each representative to schedule a group

for(int j=0;j<reprensative[i];j++){

if(j<groupCapacitysorted.length && groupCapacitysorted[j] !=0){

//Successfully Assgin group to repsentative

// Group Capacity decrease by one it means one capacity is occupied

groupCapacitysorted[j]=groupCapacitysorted[j]-1;

}else{

//Not Able to assign any group to representative.

}

}

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.