Maximum number of meetings that we can conduct [closed]

Question

This was asked during an interview to calculate the maximum number of meetings that can be held based on given 2 arrays.

Size of arrays is from 1 to 50, and the values in the array are from 1 to 1000 max.

I have an array that represents starting time for meetings - [1,3,3,5,7]. Another array that represents the time taken for the above meeting - [2,2,1,2,1]

As per the above data, the first meeting starts at 1 and continues for 2hrs. so it covers from 1hr to 3hrs as meeting duration is 2hrs. The second and third meeting starts at 3 and they continue for 2hrs or 1hrs. so they cover 3 to 5 for 2nd meeting, 3 to 4 for the third meeting. The fourth meething starts at 5 and continues for 2hrs. So it covers 5 to 7 as duration is 2hrs The last meeting starts at 7 and continues for 1hr.

The second and third are occurring at same time, so we just need to pick only one such that we can arrange maximum number of meetings.

For the given above sample data we can arrange 4 meetings.

Another example:

starting time for meetings - [1,3,5]. Time taken for meetings - [2,2,2].

Here none of the meetings can conflict so maximum we can arrange 3 meetings.

This is the code I came up with:

public static int getMaximumMeetings(List<Integer> start, List<Integer> timeTaken) {
    // Map with key as meeting start time, and value as the list of time taken values.
    Map<Integer, List<Integer>> map = new LinkedHashMap<>();
    for (int i = 0; i < start.size(); i++) {
        List<Integer> list = map.get(start.get(i));
        if (list == null) {
            list = new ArrayList<>();
        }
        list.add(timeTaken.get(i));
        map.put(start.get(i), list);
    }
    System.out.println(map);

    // Get meetings one by one
    Set<Integer> keys = map.keySet();
    Iterator<Integer> it = keys.iterator();
    Integer time = it.next();
    List<Integer> list = map.get(time);
    // Sort the time taken values so we can pick the least duration meeting
    list.sort(null);
    int count = 1;

    while (it.hasNext()) {
        List<Integer> prevList = list;
        int value = prevList.get(0);
        int prevTime = time;

        time = it.next();
        list = map.get(time);
        list.sort(null);
    // Check if total time taken for this meeting is less than the next meeting starting time.
        if (value + prevTime <= time) {
            count++;
        } else {
            time = prevTime;
            list = prevList;
        }
    }
    return count;
}

This program has cleared only 5 test cases out of 12, remaining all failed. All the test cases are hidden. So I was not clear what is wrong with this code.

Answer 1

This problem can be solved using a Greedy Approach. @Abhay already provided a good explanation, while I would like to add some code.

The following is some basic implementation example with my comments. The main idea is taken from here, which also includes complexity analysis and proof of correctness.

static int getMaximumMeetings(List<Integer> start, List<Integer> timeTaken) {
    List<Interval> list = new ArrayList<>(); // create a List of Interval
    for (int i = 0; i < start.size(); i++) {
        list.add(new Interval(start.get(i), start.get(i) + timeTaken.get(i)));
    }
    list.sort(Comparator.comparingInt(i -> i.end)); // sort by finish times ascending

    int res = 0;
    int prevEnd = Integer.MIN_VALUE; // finish time of the previous meeting

    for (Interval i : list) {
        if (i.start >= prevEnd) { // is there a conflict with the previous meeting?
            res++;
            prevEnd = i.end; // update the previous finish time
        }
    }
    return res;
}

Just an example of some Interval entity:

class Interval {
    int start;
    int end;    
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}