0 like 0 dislike
17,433 views

Image of Question :

edited | 17,433 views

0 like 0 dislike
```// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int gg = 0 ;
vector <pair<int,int>> G[200000];
// Function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<int, int>& a,
const pair<int, int>& b)
{
return (a.second < b.second);
}

// Function to find maximal disjoint set
void maxDisjointIntervals(vector<pair<int, int> > list)
{

// Sort the list of intervals
sort(list.begin(), list.end(), sortbysec);

// First Interval will always be
// included in set
//     cout << "[" << list[0].first << ", "
//         << list[0].second << "]" << endl;

gg++;
// End point of first interval
int r1 = list[0].second;

for (int i = 1; i < list.size(); i++) {
int l1 = list[i].first;
int r2 = list[i].second;

// Check if given interval overlap with
// previously included interval, if not
// then include this interval and update
// the end point of last added interval
if (l1 > r1) {
//             cout << "[" << l1 << ", "
//                 << r2 << "]" << endl;
gg++;

r1 = r2;
}
}
}

// Driver code
int main()
{
int N = 4;
//     vector<pair<int, int> > intervals = { { 1, 4 },
//                                         { 2, 4 },
//                                         { 4, 6 },
//                                         { 8, 9 } };

int n,k;
cin>>n>>k ;
int i = 0 ;
while(i<n){
int x,y,t;
cin>>x>>y>>t ;
G[t].push_back({x,y-1});
i++;
}
i = 0 ;
while(i<=100){
vector<pair<int, int> > intervals ;
int j = 0 ; int p = G[i].size();
while(j<p){
pair<int,int> yy = G[i][j];
intervals.push_back(yy);
j++;
}
//    maxDisjointIntervals(intervals);

int vv = intervals.size();
//cout<<vv<<"\n";
if(vv>=1){
maxDisjointIntervals(intervals);

}
i++;
}

cout<<gg ;
return 0;
}
```
by Expert (110,880 points)
0 like 0 dislike

# JAVA CODE:

import java.util.*;

public class MyClass {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);

//Customer
int n = in.nextInt();
//Tables
int k = in.nextInt();

List<Pair>[] ans = new ArrayList[k+1];
int count = 0;
for(int i = 1; i<k+1; i++) ans[i] = new ArrayList<>();

for(int i = 0; i<n; i++) {
int x = in.nextInt();
int y = in.nextInt();
int t = in.nextInt();

}

/**
* For every table, iterating all the customers that want them
* and getting the max possible number of people that can play
* at those tables.
*/
for(int i = 1; i<k+1; i++) {
List<Pair> intervals = ans[i];
if(intervals.size()>0) {
count += maxDisjointIntervals(intervals);
}
}

System.out.println(count);
}
/**
*Function that returns the number of people who can play at a table
*
* input -> List of people In and Out time - List<Pair> - Pair - (in, out)
*
* output -> Max no. of people who can play at the table.
*
*/

public static int maxDisjointIntervals(List<Pair> intervals) {
Collections.sort(intervals, (i1, i2)->i1.second - i2.second);

// First interval is the one with smallest out time. So this person will always get to play
int count = 1;

//The out time of first person who gets to play.
int last = intervals.get(0).second;

for(int i = 1; i<intervals.size(); i++) {
int start = intervals.get(i).first;
int end = intervals.get(i).second;
//Checking if In time of other people are less than the Out time of the previous one who had the table.
// If yes. Out time is updated to this new person's Out time.
if(start>last) {
last = end;
count++;
}
}
return count;
}

static class Pair {
//In time
int first;
//Out time
int second;

public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
}
by (140 points)