Training session will be conducted twice during the next 10 days. There are N employees (numbered from 0 to N-1) willing to attend it. Each employee has provided a list of the next 10 days they are able to attend the training. The employee preferences are represented as an array of strings. N[K] is a string consisting of digits (0-9) representing the days the kth employee is able to attend.
Need to find out the max number of employees that can attend during at least one of the two scheduled days.
For example
Given E = ["039", "4", "14", "32", "", "34", "7"], the answer is 5. It can be achieved for example by running training on days 3 and 4. This way employees number 0, 1, 2, 3 and 5 will attend the training.
Given E = ["801234567", "180234567", "0", "189234567", "891234567", "98", "9"], the answer is 7. It can be achieved for example by running training on days 0 and 9. This way employees all will attend the training.
Given E = ["5421", "245", "1452", "0345", "53", "345"], the answer is 6. It can be achieved for example by running training once on day 5. This way employees all will attend the training.
This was my test which I failed to solve.
I've tried this, but its only working for 1,2 case. Can anyone share any tips of solving it ?
public int solution(String[] E) {
Map<String, Integer> daysCount = new HashMap<String, Integer>();
int n = E.length;
for (int i = 0; i < n; i ) {
String inp = E[i];
for (int j = 0; j < inp.length(); j ) {
char c = inp.charAt(j);
if (daysCount.containsKey(Character.toString(c))) {
daysCount.merge(Character.toString(c), 1, Integer::sum);
}
else {
daysCount.put(Character.toString(c), 1);
}
}
}
Map<String, Integer> topTen = daysCount.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())).limit(2)
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
List<String> vals = new ArrayList<String>();
topTen.entrySet().forEach(entry -> {
vals.add(entry.getKey());
});
int out = 0;
StringBuilder sb = new StringBuilder();
for (int z = 0; z < vals.size(); z ) {
sb.append(vals.get(z));
}
for (int i = 0; i < n; i ) {
String inp = E[i];
if (inp.matches(".*[" sb.toString() "].*")) {
out ;
}
}
return out;
}
Update
what I've implemented, countof all days in all employee's days preferences and took the day having max count, and then checking that day is present in how many employee's days preferences.
CodePudding user response：
The trick is to identify Two distinct sets which could maximize the number of employees.
The problem in your code is, you are only comparing two sets (days) which are preferred by maximum employees. That is why, in case 2, your code is only comparing single pair (day 8 and 9) which is giving distinct set having 6 employees whereas the max distinct set is given by comparison of day 0 and 9 i.e. 7 employees.
So, you shall compare all the sets of all days without taking max 2 (This will remove all your HashMap and max logic).
Here is the code, which may not be optimized but will work
public int solution(String[] E) {
int n = E.length;
int max = 0;
for(int i=0;i <10; i )
for(int j=i 1;j<10; j ) {
//create all pairs of days one by one like 01, 02, 03, 04, 05..... 89
String sb = i "" j;
int out = 0;
for (int k = 0; k < n; k ) {
String inp = E[k];
if (inp.matches(".*[" sb.toString() "].*")) {
out ;
}
}
if(out>max) {
max=out;
}
}
return max;
}
For others who doesn't understand this, you can do it using 2D matrix.
days 0 1 2 3 4 5 6 7 8 9
emp0 1 1 1 1 1 1 1 1 1 0
emp1 1 1 1 1 1 1 1 1 1 0
emp2 1 0 0 0 0 0 0 0 0 0
emp3 0 1 1 1 1 1 1 1 1 1
emp4 0 1 1 1 1 1 1 1 1 1
emp5 0 0 0 0 0 0 0 0 1 1
emp6 0 0 0 0 0 0 0 0 0 1
Take OR of all the sets/days with each other, and take sum of all OR results. e.g. in above example, column 8 and 9 would give max distinct set i.e. 7
CodePudding user response：
I think the problem with your implementation is neglecting the fact that the day with the second most attendance after the first counting is not necessarily the second day to choose.
For example, in case of E = ["01", "01", "2"], at the first glance, 0 and 1 seem to be the good candidates for the chosen days. However, since 0 and 1 are both chosen by the same people, selecting 2 as one of the chosen days would actually maximize the number of attendants:
E = ["01", "01", "2"]
Chosen days [0,1] -> Total num of attendants is 2
Chosen days [0,2] or [1,2] -> Total num of attendants is 3
Therefore, I think you would have to calculate the attendance of the second most popular day without taking into account the preference of the employees who have already secured their seats.