TCS NQT || Coding Question and Solution || 26th August || 2022 || Set - 10 || Vishal

Question

Image of Question : 

Answer 1

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

Answer 2

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();

            ans[t].add(new Pair(x, y-1));
        }

        /**
         * 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;
        }
    }
}