HackerRank Real Estate Broker Problem Solution

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

struct AP {
    int a;  // area
    int p;  // price
};

 int nclients;
 int nhouses;
 
struct AP client[1000];
 struct AP house[1000];
 int hashouse[1000];
 int nsold = 0;

int read_int()
{
    int r, n;
    r = scanf("%d", &n);
    assert(r == 1);
    return n;
}

int compareArea(const void *a, const void *b)
{
    const struct AP *x = a;
    const struct AP *y = b;
    if (x->a != y->a)
        return x->a - y->a;
    return x->p - y->p;
}

int comparePrice(const void *a, const void *b)
{
    const struct AP *x = a;
    const struct AP *y = b;
    if (x->p != y->p)
        return x->p - y->p;
    return x->a - y->a;
}

int main()
{
    int i, j;
    nclients = read_int();
    nhouses = read_int();
    for (i = 0; i < nclients; i++) {
        client[i].a = read_int();
        client[i].p = read_int();
    }
    for (i = 0; i < nhouses; i++) {
        house[i].a = read_int();
        house[i].p = read_int();
    }
    qsort(house, nhouses, sizeof house[0], compareArea);
    qsort(client, nclients, sizeof client[0], comparePrice);
    for (i = 0; i < nhouses; i++) {
        for (j = 0; j < nclients; j++)
            if (!hashouse[j] && house[i].a >= client[j].a && house[i].p <= client[j].p) {
                hashouse[j] = 1;
                nsold += 1;
                break;
            }
    }
    printf("%d\n", nsold);
    return 0;
}

#include<bits/stdc++.h>
#define in freopen("input.txt","r",stdin)
#define out freopen("output.txt","w",stdout)

#define inp freopen(".in","r",stdin)
#define outp freopen(".out","w",stdout)

using namespace std;

#define pb push_back
#define pf push_front
#define p_f pop_front
#define p_b pop_back
#define LL long long int
#define LD long double
#define MP make_pair
#define sqr(x) (x*x)
#define nwl pr("\n")
#define fi first
#define dist(x,y,xx,yy) sqrt( (x-xx)*(x-xx)+(y-yy)*(y-yy) )
#define lenint int intsi(int x){ int cnt=0; while(x>0){cnt++;x/=10;} return (cnt); }
#define se second
#define all(v) v.begin(),v.end()
#define sc scanf
#define DEBUG(a) cout<<#a<<" -> "<<a<<endl;
#define pr printf
#define si size()
#define str strlen
#define time clock()/(double)CLOCKS_PER_SEC
#define gcd LL GCD(LL a,LL b){ if(b==0)return a;else return GCD(b,a%b); }
const int INF=(-1u)/2;
const long long int INF2=(-1ull)/2;
int a,b,c[100010],us[100010],i,j,k,n,m,timer=0,x,y;
int cnt=0,fl=0,a2,a3=-1000000,ans=0,l,r;
pair<int,int>p[100010],pp[100010];
int main()
{
//    in;
//    ios_base::sync_with_stdio(0);
	cin>>n>>m;
	for( i=0;i<n;i++ )
	{
		cin>>x>>y;
		p[i]=MP(x*-1,y);
	}
	for( i=0;i<m;i++ )
	{
		cin>>x>>y;
		pp[i]=MP(x,y*-1);
	}
	sort(pp,pp+m);
	sort(p,p+n);
	for( i=0;i<m;i++ )pp[i].se*=-1;
	for( i=0;i<n;i++ )p[i].fi*=-1;
	for( i=0;i<n;i++ )
	{
		fl=-1;
		for( j=0;j<m;j++ )
		{
			if( us[j] )continue;
			if( pp[j].fi>p[i].fi && pp[j].se<=p[i].se )
			{
				if( fl==-1 )fl=j;
				if( pp[j].se>pp[fl].se )fl=j;
			}
		}
		if(fl!=-1)
		{
			us[fl]=1;
			ans++;
		}
	}
	cout<<ans<<endl;
    return 0;
}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    
    
    
    static int INFINITE = Int32.MaxValue;
    static int NILL = 0;
    
    public struct Client
    {
        public int idx, area, prize, nill_id;

        public Client(int p_idx, int p_area, int p_prize)
        {
            idx = p_idx;
            area = p_area;
            prize = p_prize;
            nill_id = 0;
        }
    }
    
    public struct House
    {
        public int idx, area, prize, nill_id;

        public House(int p_idx, int p_area, int p_prize)
        {
            idx = p_idx;
            area = p_area;
            prize = p_prize;
            nill_id = 0;
        }
    } 
    
    static int max(int n, int m) {
        if(n>m) return n;
        else return m;
    }
    
    static List<int>[] buildGraph(int n, int m,IEnumerable<Client> clients, IEnumerable<House> houses) {
        List<int>[] graph = new List<int>[n+1];
        IEnumerable<int> relatedHouses;
        for(int i=0; i<=n; i++) {
            graph[i] = new List<int>();
        }
        
        var query = from client in clients 
                      join house in houses 
                      on client.nill_id equals house.nill_id 
                      where client.area <= house.area
                         && client.prize >= house.prize
                      select new { cIndex = client.idx, hIndex =  house.idx };
        
        var agroupedData = query.GroupBy(x => x.cIndex)
                                .Select(y => new {cIndex = y.Key, 
                                                  rHouses = y.ToList()}
                                        );
        foreach(var x in agroupedData) {
            graph[x.cIndex].AddRange(x.rHouses.Select(y => y.hIndex));
        }
        
        return graph;
        
    }
    
    static bool bfs(List<int>[] graph, int[] pairU, int[] pairV, int[] dist) {
        Queue<int> queue = new Queue<int>();
        int u;
        for(int i=1; i<pairU.Length; i++) {
            // free vertex are marked
            if(pairU[i]==NILL) {
                dist[i]=0;
                queue.Enqueue(i);
            }
            
            else dist[i]=INFINITE;
        }
        
        dist[NILL] = INFINITE;
        
        while(queue.Any()) {
            u = queue.Dequeue();
            
            if(dist[u] < dist[NILL]) {
                foreach(int v in graph[u]) {
                    // edge not yet considered
                    if(dist[pairV[v]] == INFINITE) {
                        dist[pairV[v]] = dist[u] + 1;
                        queue.Enqueue(pairV[v]);
                    }
                }
            }
        }
        
        //  an augmenting path has been founded
        return dist[NILL] != INFINITE;
    }
    
    
    static bool dfs(int u, List<int>[] graph, int[] pairU, int[] pairV, int[] dist) {
        if(u != NILL) {
          foreach(int v in graph[u]) {
            if(dist[pairV[v]] == dist[u]+1) {
               if(dfs(pairV[v], graph, pairU, pairV, dist)) {
                        pairV[v] = u;
                        pairU[u] = v;
                        return true;
                    }
                }
          }
          dist[u]=INFINITE;
          return false;
        }
        return true;
  }
    
    

    static int realEstateBroker(int n, int m, List<Client> clients, List<House> houses) {
        int[] pairU = new int[n+1];
        int[] pairV = new int[m+1];
        int[] dist = new int[n+1];
 
        for (int u=0; u<n; u++)
            pairU[u] = NILL;
        for (int v=0; v<m; v++)
            pairV[v] = NILL;

        int result = 0;
        
        List<int>[] graph = buildGraph(n, m,clients, houses);
        
        while(bfs(graph, pairU, pairV, dist)) {
            for(int u=1; u<=n; u++) {
                if(pairU[u]==NILL && dfs(u, graph, pairU, pairV, dist)) {
                    result++;
                }
            }
        }
        
        return result;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
        
        string[] nm = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nm[0]);

        int m = Convert.ToInt32(nm[1]);

        List<Client> clients = new List<Client>();
    
        int idx;
        int[] clientData;
        for (int clientsRowItr = 0; clientsRowItr < n; clientsRowItr++) {
            idx=clientsRowItr;
            clientData = Array.ConvertAll(Console.ReadLine().Split(' '), clientsTemp => Convert.ToInt32(clientsTemp));
            clients.Add(new Client(++idx, clientData[0], clientData[1]));
        }

        List<House> houses = new List<House>();
        int[] houseData;
        for (int housesRowItr = 0; housesRowItr < m; housesRowItr++) {
            idx=housesRowItr;
            houseData = Array.ConvertAll(Console.ReadLine().Split(' '), housesTemp => Convert.ToInt32(housesTemp));
            houses.Add(new House(++idx, houseData[0], houseData[1]));
            
        }

    int result = realEstateBroker(n, m, clients, houses);
    

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
    static class Client implements Comparable<Client> {
        int minX, maxY;

        public Client(int minX, int maxY) {
            this.minX = minX;
            this.maxY = maxY;
        }

        @Override
        public int compareTo(Client o) {
            return (o.minX == this.minX) ? this.maxY - o.maxY : this.minX - o.minX;
        }
    }

    static class House implements Comparable<House> {
        int x, y;

        public House(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(House o) {
            return (o.x == this.x) ? this.y - o.y : this.x - o.x;
        }
    }

    static int realEstateBroker(int[][] clients0, int[][] houses0) {
        int cc = clients0.length;
        int hc = houses0.length;
        List<Client> cs = new ArrayList<>(cc+1);
        List<House> hs = new ArrayList<>(hc+1);
        for (int a[] : clients0) cs.add(new Client(a[0], a[1]));
        for (int a[] : houses0) hs.add(new House(a[0], a[1]));
        Collections.sort(cs);
        Collections.sort(hs);
        cs.add(new Client(Integer.MAX_VALUE, Integer.MAX_VALUE));

        int c = 0;
        int h = 0;
        int sold = 0;
        TreeSet<Long> ts = new TreeSet<>(); // unique min price
        while (c < cc && h < hc) {
            while (h < hc && hs.get(h).x <= cs.get(c).minX)
                h++;
            if (h >= hc)
                break;
            while (c < cc && hs.get(h).x > cs.get(c).minX) {
                ts.add(cs.get(c).maxY * 1000L + c);
                c++;
            }
            while (h < hc && hs.get(h).x <= cs.get(c).minX) {
                Long g = ts.ceiling(hs.get(h).y * 1000L);
                if (g != null) {
                    ts.remove(g);
                    sold++;
                }
                h++;
            }
        }
        return sold;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nm[0].trim());

        int m = Integer.parseInt(nm[1].trim());

        int[][] clients = new int[n][2];

        for (int clientsRowItr = 0; clientsRowItr < n; clientsRowItr++) {
            String[] clientsRowItems = scanner.nextLine().split(" ");

            for (int clientsColumnItr = 0; clientsColumnItr < 2; clientsColumnItr++) {
                int clientsItem = Integer.parseInt(clientsRowItems[clientsColumnItr].trim());
                clients[clientsRowItr][clientsColumnItr] = clientsItem;
            }
        }

        int[][] houses = new int[m][2];

        for (int housesRowItr = 0; housesRowItr < m; housesRowItr++) {
            String[] housesRowItems = scanner.nextLine().split(" ");

            for (int housesColumnItr = 0; housesColumnItr < 2; housesColumnItr++) {
                int housesItem = Integer.parseInt(housesRowItems[housesColumnItr].trim());
                houses[housesRowItr][housesColumnItr] = housesItem;
            }
        }

        int result = realEstateBroker(clients, houses);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the realEstateBroker function below.
 */
function realEstateBroker(clients, houses) {
  houses.sort((a, b) => a[0] - b[0]);
  clients.sort((a, b) => a[1] - b[1]);
  let count = 0;
  for (let ci = 0; ci < clients.length && houses.length; ci++) {
    const [area, price] = clients[ci];
    let l = 0;
    let r = houses.length;
    while (l < r) {
      const m = l + ((r - l) >>> 1);
      const houseArea = houses[m][0];
      // console.log({text: 'bef', area, price, l, r, m, houseArea})
      if (houseArea <= area) {
        l = m + 1;
      } else {
        r = m;
      }
      // console.log({text: 'aft', area, price, l, r, m, houseArea})
    }
    // console.log({area, price, l, houses});
    for (let i = l; i < houses.length; i++) {
      const housePrice = houses[i][1];
      if (housePrice <= price) {
        count++;
        houses.splice(i, 1);
        break;
      }
    }
  }
  // console.log({visited})
  return count;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nm = readLine().split(' ');

    const n = parseInt(nm[0], 10);

    const m = parseInt(nm[1], 10);

    let clients = Array(n);

    for (let clientsRowItr = 0; clientsRowItr < n; clientsRowItr++) {
        clients[clientsRowItr] = readLine().split(' ').map(clientsTemp => parseInt(clientsTemp, 10));
    }

    let houses = Array(m);

    for (let housesRowItr = 0; housesRowItr < m; housesRowItr++) {
        houses[housesRowItr] = readLine().split(' ').map(housesTemp => parseInt(housesTemp, 10));
    }

    let result = realEstateBroker(clients, houses);

    ws.write(result + "\n");

    ws.end();
}

n, m = map(int, input().split())
buy, house = [], []
for i in range(n):
    buy.append(tuple(map(int, input().split())))
for i in range(m):
    house.append(tuple(map(int, input().split())))
buy.sort(key=lambda x: x[1])
house.sort()
sold = [False for i in range(n)]
a = 0
for h in range(m):
    for c in range(n):
        if not sold[c]:
            if buy[c][0] <= house[h][0] and buy[c][1] >= house[h][1]:
                sold[c] = True
                a += 1
                break
print(a)