Site icon EasyLearnCode

N meetings in one room

Java


class Pair {
    int start;
    int end;
    
    Pair(int start, int end) {
        this.start = start;
        this.end = end;
    }
    
}
class Solution 
{
    //Function to find the maximum number of meetings that can
    //be performed in a meeting room.
    public static int maxMeetings(int start[], int end[], int n)
    {
        // add your code here
        ArrayList<Pair> meetings = new ArrayList<>();
        for(int i=0; i<start.length; i++) {
            Pair temp = new Pair(start[i], end[i]);
            meetings.add(temp);
        }
        
        // sort;
        Collections.sort(meetings, new Comparator<Pair>() {
            public int compare(Pair o1, Pair o2){
                if (o1.end < o2.end) 
                    return -1;
                else if (o1.end > o2.end) //  1 -> swap
                    return 1;
                return 0;
            }
        });
        
        int answer=1;
        int preed = meetings.get(0).end;
        
        for(int i=1; i<meetings.size(); i++){
            Pair temp = meetings.get(i);
            int st = temp.start;
            if(st > preed){
                answer++;
                preed=temp.end;
            }
        }
        return answer;
    }
}

C++

#include <bits/stdc++.h>

using namespace std;

void maxMeetings(int *, int *, int);

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int start[n], end[n];
        for (int i = 0; i < n; i++) cin >> start[i];

        for (int i = 0; i < n; i++) cin >> end[i];

        maxMeetings(start, end, n);
        cout << endl;
    }
    return 0;
}// } Driver Code Ends


void maxMeetings(int start[], int end[], int n) {
   priority_queue <pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> v;
    vector<pair<int,pair<int,int>>> ans;
    for(int i=0;i<n;i++){
        v.push({end[i],{i+1,start[i]}});
    }

    ans.push_back({v.top().first,{v.top().second.first,v.top().second.second}});
    v.pop();
    for(int i=1;i<n;i++){
        if(v.top().second.second>ans[ans.size()-1].first)
        ans.push_back({v.top().first,{v.top().second.first,v.top().second.second}});
        v.pop();
    }

    for(int i=0;i<ans.size();i++)
    cout<<ans[i].second.first<<" ";
}

Python

class Pair:
    def __init__(self, start, end):
        self.start = start
        self.end = end

def max_meetings(start, end, n):
    meetings = []
    for i in range(n):
        temp = Pair(start[i], end[i])
        meetings.append(temp)
        
    # sort
    meetings.sort(key=lambda x: x.end)
    
    answer = 1
    preed = meetings[0].end
    
    for i in range(1, len(meetings)):
        temp = meetings[i]
        st = temp.start
        if st > preed:
            answer += 1
            preed = temp.end
    
    return answer
Share
Exit mobile version