Maximum number of meetings that we can conduct

user_3181365 0
Viewed 10656

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.

algorithm java
3 Answers

Its a classical "interval scheduling problem". Your approach is going for the meeting with shortest duration.

Shortest duration doesn't give optimal output. One of the examples could be intervals (in form start time-end time)

1-11, 10-12, 13-20, 21-30, 29-32,31-40

It can be proven that optimal solution is when you choose shortest finish time first.

Use this algo Sort the elements by finish time. Use greedy and include the first interval. Mark its end time.

If second interval starts after end time, include it as well and update end time. Else move on to third interval.

Continue with the approach.

You'll get the number of meetings along with the list of meetings

user_102814560

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;
    }
}
user_26682320

I could think of the following problems that you didnt consider (despite your algorithmic idea was not correct, which would be the main issue):

  1. No input validation: You don't have checks if all values of the input (here list) are in range between 1 and 50. Negative values in the time array would be crucial for the result. Neither you check if both input lists have the same length.
  2. Were there further restrictions? Like how many hours the interview period has. You dont have any checks for that.
  3. When you build the map and have two interviews which start at the same time you always would take the first interview, no matter of the duration. By that if the first interview takes more time then the second, you waste a lot of time.

To be fair, your could is very hard readable.

user_100344250
Related