The Problem
Following our team check-in, we break off in to co-ordination meetings with (n) participants covering various (uniquely named) Topics.
Currently, people stand around trying to self organize and we are not maximizing concurrency of meetings, and/or releasing team members as soon as possible to return to work.
We keep a list of all co-ordination meetings that come out of the check-ins in a Google Spreadsheet:
+-----------------------------------------------------------+
| Meetings |
+-----------------------------------------------------------+
| Topic A | Topic B | Topic C | Topic D | Topic E |
+-----------------------------------------------------------+
| Billy | JD | David | Tania | JB |
| Mel | Rowan | Emily | David | Fred |
| Tracey | Mike | | Mike | Tania |
| JB | Aaron | | Fred | |
| Luke | Billy | | | |
| Aaron | | | | |
| Michael | | | | |
+-----------------------------------------------------------+
As a starting point, I have (surely quite inefficient) code that iterates over every meeting and returns an array of pairs that have no participant clashes.
Example output from main() with above as input data (don't worry all code is below):
[["Topic A","Topic C"],["Topic A","Topic D"],["Topic B","Topic C"],["Topic B","Topic E"],["Topic C","Topic E"]]
What I Need
Ideally, I need a solution that returns an array ordered by most meetings possible to be run at once. Either using the array of pairs returned from main() or an entirely other method using the data in the spreadsheet as input.
In my example here, it would take the form:
[[Topic B, Topic C, Topic E],[Topic A, Topic D]]
I'll then group these visually by colour in the Google Spreadsheet so staff can see.
I attempted to create some code (main2()) that reduces the array based on mutually exclusive pairs, but it is plain wrong. Eg: That code outputs:
[["Topic A","Topic C","Topic B","Topic E"],"Topic D"]
...which is incorrect as A and B obviously have a clash. (A and C, B and E would be fine consecutively of course).
My Current Code
function onOpen () {
var ui = SpreadsheetApp.getUi();
ui.createMenu('Meeting Tools')
.addItem('Compute Optimal Meeting Order', 'main')
.addToUi();
}
function main() {
var ss = SpreadsheetApp.getActive();
var sss = ss.getActiveSheet();
//var sss = ss.getSheetByName("Sheet3");
var data = sss.getDataRange().getValues();
var ui = SpreadsheetApp.getUi();
var meetings = {};
var pairs = [];
var objKey;
// Structuring data to obj
for (var x=0; x < sss.getLastColumn(); x++) {
for (var y=1; y < data.length; y++) {
if (y==1) {
objKey = data[y][x];
meetings[objKey] = [];
}
else if (data[y][x]) {
meetings[objKey].push(data[y][x]);
}
}
}
var keys = Object.keys(meetings).sort();
var loc;
// Starting with "A"
for (var m in meetings) {
if (!meetings.hasOwnProperty(m)) continue;
Logger.log("-----------------------------");
Logger.log("SCANNING: " + m);
Logger.log("-----------------------------");
loc = keys.indexOf(m);
// check A, B, C, D, E
for (var m2 = 0; m2 < keys.length; m2++) {
var pointer = (m2 + loc) % keys.length;
// DO NOT CHECK SAME MEETING
if (keys[pointer] == m) {
Logger.log("||||||||| WE ARE COMPARING OURSELVES: (" + keys[pointer] + "/" + m + "). SKIPPING!");
continue;
}
// FOR EACH PARTICIPANT OF CURRENT MEETING
for (var p = 0; p < meetings[m].length; p++) {
Logger.log("");
Logger.log(" >>> COMPARING " + keys[pointer]);
Logger.log(" >>> >>> " + meetings[m][p] + " " + (p+1) +"/"+meetings[m]. length);
// SEEK THE LOCATION OF THE MEETING PARTICIPANT IN THE NEXT MEETING
var testIndex = meetings[keys[pointer]].indexOf(meetings[m][p]);
// IF THE MEETING PARTICIPANT IS ALSO IN THE NEXT MEETING
if (testIndex > -1) {
Logger.log("We have a match! Meeting "+ m + " has participant " + meetings[m][p] + " which unfortunately clashes with meeting " + keys[ pointer]);
Logger.log("Therefore Meeting " + m + " cannot run at the same time as " + keys[pointer]);
Logger.log("We need to bail out of compairing against: " + keys[pointer ]);
// WE BAIL OUT AS WE HAVE A CLASH
break;
}
// IF THE MEETING PARTICIPANT IS NOT IN THE NEXT MEETING AND WE HAVE CHECKED EVERYONE. WE SHOULD BE GOOD.
else if (testIndex == -1 && p+1 == meetings[m].length) {
Logger.log("This looks to be clear!!! Adding to pair group.");
pairs.push([m,keys[pointer]]);
}
}//loop
} //loop
} //obj_loop
// Logger.log("FINAL TALLY: " + JSON.stringify(pairs));
Logger.log("FINAL TALLY (CLEANED): " + JSON.stringify(removeRepeats(pairs.sort()) ));
// ui.alert(JSON.stringify(removeRepeats(pairs.sort())));
// ss.toast(JSON.stringify(removeRepeats(pairs.sort())));
// debugger;
return removeRepeats(pairs.sort());
}
function main2(array) {
// DEBUG
// array = [["A","C"],["A","D"],["B","C"],["B","E"],["C","E"]];
// array = [["A","C"],["A","D"],["B","C"],["B","E"],["C","E"]];
array = main();
var holdingArr = [];
for (var i = array.length - 1; i >= 1; i--) {
//DEBUG
//var pair = ["Z","X"];
var pair = array[i];
if (arrayPairCheck([array[0]], pair)) {
holdingArr.push(pair);
array.pop(i);
}
else {
array[0] = array[0].concat(array[i]);
array.pop(i);
}
} //loop
if (holdingArr && holdingArr.length > 0) {
for (var j=0; j < holdingArr.length; j++) {
var checkIndex = holdingMeetingExistsInPair(array[0],holdingArr[j]);
if (checkIndex !== false) {
array.push(holdingArr[j][checkIndex]);
}
} //loop
}
// DEBUG
debugger;
Logger.log(JSON.stringify(array));
}
function holdingMeetingExistsInPair(arrayFirstIndexGroup,holdingArrPair) {
if (arrayFirstIndexGroup && arrayFirstIndexGroup.length > 0) {
if (arrayFirstIndexGroup.indexOf(holdingArrPair[0]) === -1) {
return 0;
}
if (arrayFirstIndexGroup.indexOf(holdingArrPair[1]) === -1) {
return 1;
}
}
return false;
}
function arrayPairCheck(array,pair) {
// DEBUG
// array = [["A","C"],["A","D"],["B","C"],["B","E"],["C","E"]];
// pair = ["Z","X"];
var seen = false;
if (array && array.length > 0) {
for (var i=0; i < array.length; i++) {
array[i].map(function(item,item2) {
if (item === pair[0] || item === pair[1]) {
seen = true;
return true;
}
});
} //loop
}
if (seen) { return true; } else { return false; }
}
// http://stackoverflow.com/questions/27734661/javascript-arrays-ab-ba
function removeRepeats(list) {
var i;
var b = [];
var _c = [];
for (i = 0; i < list.length; i++) {
var a = list[i].sort();
var stra = a.join("-");
if(_c.indexOf(stra) === -1) {
b.push(a);
_c.push(stra);
}
}
return b;
}
Lastly
Some avenues I've been reading about to piece together an understanding are below. My rep is too low to link these. Someone may confrim this is a direction to pursue?
Hopcroft–Karp algorithm
Thank you for any time spent on this.
UPDATE 1
For the following, the solution should correctly have meeting order set as:
1) W, X, Z
2) V, Y
+-----------------------------------------------------------+
| Meetings |
+-----------------------------------------------------------+
| Topic V | Topic W | Topic X | Topic Y | Topic Z |
+-----------------------------------------------------------+
| Billy | JD | David | Tania | JB |
| Mel | Rowan | Emily | David | Fred |
| Tracey | Mike | | Mike | |
| JB | | | Fred | |
| Luke | | | | |
| Aaron | | | | |
| Michael | | | | |
+-----------------------------------------------------------+
