Найдите максимальное количество людей, которые могут присутствовать на собрании

Опубликовано: 25 Февраля, 2023

Существует только одна комната, в которой проводятся N встреч, заданных в виде интервалов вида (начало[i], конец[i], люди[i]), где начало[i] — время начала i- й встречи, конец [i] — время окончания i -го собрания, people[i] — количество людей, которые могут присутствовать на i- м собрании. В любой момент времени комната может быть занята только одним собранием, т.е. если два собрания имеют перекрывающиеся интервалы, то можно выбрать только одно из них. Задача состоит в том, чтобы найти максимальное количество людей, которые могут присутствовать на собрании.

Примеры:

Input: Meetings = { {5, 8, 3}, {1, 4, 5}, {7, 10, 2} }
Outputs: 8
Explanation: The optimal meetings are {1, 4, 5} and {5, 8, 3}.
So, 5+3 = 8 is the maximum number of people.

Input: Meetings = { {1, 5, 20}, {3, 8, 50}.{6, 10, 70} }
Output: 90
Explanation: The optimal meetings are {1, 5, 20}, {6, 10, 70}.
So, 20 + 70 = 90 is the maximum number of people.

Подход: проблема может быть решена с помощью динамического программирования на основе следующего наблюдения:

Process the meetings by sorting in a non-decreasing order of the end time as it is optimal to first process the meeting that gets over the earliest. We can use Dynamic Programming to solve this problem.

Create a dp[] array where dp[i] = maximum number of people who can attend the meeting till the ith meeting. At any particular point i, check if the ith meeting overlaps with the (i-1)th meeting. 

  • If there is no overlap dp[i] = dp[i-1] + people[i] ( maximum number of people possible till i-1 + people[i])
  • Otherwise, dp[i] = max( dp[i-1], dp[j] + people[i] ) (maximum number of people possible till i-1 or maximum number of people possible till some jth meeting which is nearest non-overlapping meeting with i where j < i.

We can use binary search to find j.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Сортируйте встречи по времени окончания встреч.
  • Начните итерацию с начала отсортированного массива встреч.
    • Для каждого индекса соблюдайте указанное выше соотношение.
    • Если соседние интервалы перекрываются, используйте двоичный поиск в префиксе, чтобы найти j .
  • Верните значение, хранящееся в dp[N-1], в качестве требуемого ответа.

Ниже приведена реализация описанного выше подхода.

C++




// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number of people
int maxPeople(vector<vector<int> >& data, int n)
{
    // Sorting the intervals according to
    // the end time in non decreasing order
    sort(data.begin(), data.end(),
         [&](vector<int> a, vector<int> b) {
             if (a[1] == b[1])
                 return a[0] < b[0];
             else
                 return a[1] < b[1];
         });
 
    vector<int> dp(n, 0);
    dp[0] = data[0][2];
 
    // Need a map to store the highest possible value
    // for same end timed intervals
    map<int, int> mp;
 
    // First interval is assumed to be taken at first
    // the highest value with its ending time is dp[0]
    mp[data[0][1]] = dp[0];
    for (int i = 1; i < n; i++) {
        int curstart = data[i][0];
        int curend = data[i][1];
 
        // If the ith interval overlaps with
        // the (i-1)th interval
        if (curstart <= data[i - 1][1]) {
 
            // Binary search for an interval that has
            // its ending time just lesser than
            // the starting time of the ith interval
            int left = 0;
            int right = i;
            int var = data[i][0];
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (data[mid][1] < var)
                    left = mid;
                else
                    right = mid - 1;
            }
            // We have two choice either we don"t pick
            // the ith interval then dp[i-1] or we pick
            // the ith interval then dp[left]+ith value.
            // We use mp[data[left][1]] instead of
            // dp[left] since our map stores the maximum of
            // the dp values that end with a given end time.
            dp[i] = max(dp[i - 1],
                        mp[data[left][1]] + data[i][2]);
 
            // Update the map with max of current dp
            // value and mp[data[i][1]] accounting for an
            // interval that may have higher dp value ending
            // with the same end time as the ith interval.
            mp[data[i][1]] = max(dp[i], mp[data[i][1]]);
        }
        else {
            dp[i] = dp[i - 1] + data[i][2];
            mp[data[i][1]] = max(mp[data[i][1]], dp[i]);
        }
    }
 
    // Return the required answer
    return dp[n - 1];
}
 
// Driver code
int main()
{
    vector<vector<int> > Meetings
        = { { 5, 8, 3 }, { 1, 4, 5 }, { 7, 10, 2 } };
    int N = Meetings.size();
 
    // Function call
    cout << maxPeople(Meetings, N);
    return 0;
}

Java



/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
// sorting a list of list
class ListComparator<T extends Comparable<T> >
  implements Comparator<List<T> > {
 
  @Override public int compare(List<T> o1, List<T> o2)
  {
    for (int i = 0; i < Math.min(o1.size(), o2.size());
         i++) {
      int c = o1.get(i).compareTo(o2.get(i));
      if (c != 0) {
        return c;
      }
    }
    return Integer.compare(o1.size(), o2.size());
  }
}
 
class GFG {
 
  // Function to find the maximum number of people
  public static int maxPeople(List<List<Integer> > data,
                              int n)
  {
    // Sorting the intervals according to
    // the end time in non decreasing order
    Collections.sort(data, new ListComparator<>());
 
    List<Integer> dp = new ArrayList<Integer>();
    for (int i = 0; i < n; i++) {
      dp.add(0);
    }
    dp.set(0, data.get(0).get(2));
 
    // Need a map to store the highest possible value
    // for same end timed intervals
 
    Map<Integer, Integer> mp
      = new HashMap<Integer, Integer>();
 
    for (int i = 0; i < 15; i++) {
      mp.put(i, 0);
    }
 
    // First interval is assumed to be taken at first
    // the highest value with its ending time is dp[0]
    mp.put(data.get(0).get(1), dp.get(0));
    for (int i = 1; i < n; i++) {
      int curstart = data.get(i).get(0);
      int curend = data.get(i).get(1);
 
      // If the ith interval overlaps with
      // the (i-1)th interval
      if (curstart <= data.get(i - 1).get(1)) {
 
        // Binary search for an interval that has
        // its ending time just lesser than
        // the starting time of the ith interval
        int left = 0;
        int right = i;
        int var = data.get(i).get(0);
        while (left < right) {
          int mid = left + (right - left) / 2;
          if (data.get(mid).get(1) < var)
            left = mid;
          else
            right = mid - 1;
        }
        // We have two choice either we don"t pick
        // the ith interval then dp[i-1] or we pick
        // the ith interval then dp[left]+ith value.
        // We use mp[data[left][1]] instead of
        // dp[left] since our map stores the maximum
        // of the dp values that end with a given
        // end time.
        dp.set(i, Math.max(
          dp.get(i - 1),
          mp.get(data.get(left).get(1))
          + data.get(i).get(2)));
 
        // Update the map with max of current dp
        // value and mp[data[i][1]] accounting for
        // an interval that may have higher dp value
        // ending with the same end time as the ith
        // interval.
        mp.put(
          data.get(i).get(1),
          Math.max(dp.get(i),
                   mp.get(data.get(i).get(1))));
      }
      else {
        dp.set(i,
               dp.get(i - 1) + data.get(i).get(2));
        mp.put(data.get(i).get(1),
               Math.max(mp.get(data.get(i).get(1)),
                        dp.get(i)));
      }
    }
 
    // Return the required answer
    return dp.get(n - 1);
  }
 
  public static void main(String[] args)
  {
    List<List<Integer> > Meetings = new ArrayList<>();
 
    List<Integer> a = new ArrayList<Integer>();
    a.add(5);
    a.add(8);
    a.add(3);
    Meetings.add(a);
 
    List<Integer> b = new ArrayList<Integer>();
    b.add(1);
    b.add(4);
    b.add(5);
    Meetings.add(b);
 
    List<Integer> c = new ArrayList<Integer>();
    c.add(7);
    c.add(10);
    c.add(2);
    Meetings.add(c);
 
    int N = Meetings.size();
 
    // Function call
    System.out.println(maxPeople(Meetings, N));
  }
}
 
// This code is contributed by akashish__
Python3



# Python code to implement the approach
 
# Function to find the maximum number of people
def maxPeople(data,n):
    # Sorting the intervals according to
    # the end time in non decreasing order
    data.sort(key=lambda a:a[1])
     
    dp=[0]*n
    dp[0]=data[0][2]
     
    # Need a map to store the highest possible value
    # for same end timed intervals
    mp=[0]*15
     
    # First interval is assumed to be taken at first
    # the highest value with its ending time is dp[0]
    mp[data[0][1]]=dp[0]
     
    for i in range(1,n):
        curstart=data[i][0]
        curend=data[i][1]
         
        # If the ith interval overlaps with
        # the (i-1)th interval
        if(curstart<=data[i-1][1]):
            # Binary search for an interval that has
            # its ending time just lesser than
            # the starting time of the ith interval
            left=0
            right=i
            var=data[i][0]
            while(left<right):
                mid=left+(right-left)//2
                if(data[mid][1]<var):
                    left=mid
                else:
                    right=mid-1
             
            # We have two choice either we don"t pick
            # the ith interval then dp[i-1] or we pick
            # the ith interval then dp[left]+ith value.
            # We use mp[data[left][1]] instead of
            # dp[left] since our map stores the maximum of
            # the dp values that end with a given end time.
            dp[i]=max(dp[i-1],mp[data[left][1]]+data[i][2])
             
             
            # Update the map with max of current dp
            # value and mp[data[i][1]] accounting for an
            # interval that may have higher dp value ending
            # with the same end time as the ith interval.
            mp[data[i][1]]=max(dp[i],mp[data[i][1]])
             
         
        else:
            dp[i]=dp[i-1]+data[i][2]
            mp[data[i][1]]=max(mp[data[i][1]],dp[i])
             
    # Return the required answer
    return dp[n-1]
     
# Driver code
 
Meetings=[[5,8,3],[1,4,5],[7,10,2]]
N=len(Meetings)
 
# Function call
print(maxPeople(Meetings,N))
 
# This code is contributed by Pushpesh raj.
C#

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ