(GREEDY) N meetings in one room

//{ Driver Code Starts
import java.io.*;
import java.lang.*;
import java.util.*;

class GFG {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());

        while (t-- > 0) {
            String line1 = br.readLine();
            String[] a1 = line1.trim().split("\\s+");
            int n = a1.length;
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(a1[i]);
            }

            String line2 = br.readLine();
            String[] a2 = line2.trim().split("\\s+");
            n = a2.length;
            int b[] = new int[n];
            for (int i = 0; i < n; i++) {
                b[i] = Integer.parseInt(a2[i]);
            }

            int ans = new Solution().maxMeetings(a, b);
            System.out.println(ans);
            System.out.println("~");
        }
    }
}

// } Driver Code Ends

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 int maxMeetings(int start[], int end[]) {
        Pair[] pairs = new Pair[start.length];
        for (int i = 0; i < start.length; i++) {
            pairs[i] = new Pair(start[i], end[i]);
        }

        // Step 2: Sort pairs based on the end values
        Arrays.sort(pairs, Comparator.comparingInt(p -> p.end));
        
        for (int i = 0; i < start.length; i++) {
            start[i] = pairs[i].start;
            end[i] = pairs[i].end;
        }
        
        int prev_end = end[0], ans = 1;
        for(int i=1;i<start.length;++i)
        {
            if(start[i] > prev_end)
            {
                ans++;
                prev_end = end[i];
            }
        }
        
        return ans;
    }
}