Table of Contents
Real Estate Broker – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
using namespace std;
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <limits.h>
#include <vector>
#include <map>
#include <bitset>
#include <string>
#include <iterator>
#include <set>
#include <utility>
#include <queue>
#include <numeric>
#include <functional>
#include <ctype.h>
#include <stack>
#include <algorithm>
#include <cstdlib>
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define wl(n) while(n--)
#define ll long long
#define bitcnt(x) __builtin_popcount(x)
#define P(x) printf("%d\n",x)
#define PB push_back
#define MP make_pair
#define fl(i,n) for(i=0;i<n;i++)
#define fil(i,a,n) for(i=a;i<n;i++)
#define rev(i,a,n) for(i=n-1;i>=a;i--)
#define mem(a,i) memset(a,i,sizeof(a))
#define F first
#define S1 second
typedef pair<int,int> P;
vector<int> v1[100009];
pair<int,int> p1;
#define MOD 1000000007
#define debug(x) printf("####%d####\n",x);
#define nl printf("\n");
#define str string
#define N 100000
int a[1234567],b[N],c[N],d[N];
string s;
int dp[1001];
ll pow1(ll x,ll y)
{
if(y==0)
return 1;
ll temp= pow1(x,y/2)%MOD;
if(y%2==0)
return (temp*temp)%MOD;
else
return (((temp*temp)%MOD)*x)%MOD;
}
// hopcraft_karp algorithm for maximum matching
int dist[100009],match[100009],n,m;
bool bfs()
{
int i,j;
queue<int> q1;
for(i=1;i<=n;i++)
{
if(match[i]==0)
{
dist[i]=0;
q1.push(i);
}
else
dist[i]=INT_MAX;
}
dist[0]=INT_MAX;
while(!q1.empty())
{
int u=q1.front();
q1.pop();
if(u!=0) // 0 has no adjacency list
{
fl(i,v1[u].size())
{
int p=v1[u][i];
if(dist[match[p]]==INT_MAX) // if match[p] is not dere toh it would be zero by default
{
dist[match[p]]=dist[u]+1;
q1.push(match[p]);
}
}
}
}
// this ensures ki ek toh path h he i.e augmenting path because kisi ek ka toh match[i] will be equal to 0
return dist[0]!=INT_MAX;
}
bool dfs(int u)
{
if(u==0)
return true; // base case always true
int i;
fl(i,v1[u].size())
{
int p=v1[u][i];
if(dist[match[p]]==dist[u]+1) // to ensure ki jo path bfs se mila tha augumenting ye vahi vaala h
{
if(dfs(match[p]))
{
match[p]=u; // means we found a path of alternating edges and changing the matched ones to unmatched and vice versa
match[u]=p;
return true;
}
}
}
return false; // else this is not the path
}
int hopcraft_karp()
{
int ans=0,i;
while(bfs())
{
for(i=1;i<=n;i++)
{
if(match[i]==0&&dfs(i))
ans++;
}
}
return ans;
}
int main()
{
//std::ios_base::sync_with_stdio(false);
int t;
int i,j,k,l;
S2(n,m);
fl(i,n)
S2(a[i],b[i]);
fl(i,m)
S2(c[i],d[i]);
fl(i,n)
{
// >=a[i] , <=b[i]
fl(j,m)
{
if(c[j]>=a[i]&&d[j]<=b[i])
{
v1[i+1].push_back(j+1+n);
v1[j+1+n].push_back(i+1);
}
}
}
P(hopcraft_karp());
return 0;
}
Java Real Estate Broker HackerRank Solution
import java.io.*;
import java.util.*;
public class e {
public static void main(String[] args) throws IOException {
input.init(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = input.nextInt(), m = input.nextInt();
int[] as = new int[n], ps = new int[n];
for(int i = 0; i<n; i++)
{
as[i] = input.nextInt();
ps[i] = input.nextInt();
}
int[] xs = new int[m], ys = new int[m];
for(int i = 0; i<m; i++)
{
xs[i] = input.nextInt();
ys[i] = input.nextInt();
}
TidalFlow tf = new TidalFlow(n+m);
for(int i = 0; i<n; i++) tf.add(tf.s, i, 1);
for(int i = 0; i<m; i++) tf.add(i+n, tf.t, 1);
for(int i = 0; i<n; i++)
for(int j = 0; j<m; j++)
{
if(xs[j] > as[i] && ys[j] <= ps[i])
tf.add(i, j+n, 1);
}
out.println(tf.getFlow());
out.close();
}
static class TidalFlow {
ArrayDeque<Edge> stk = new ArrayDeque<Edge>();
int N, s, t, oo = 987654321, fptr, bptr;
ArrayList<Edge>[] adj;
int[] q, dist, pool;
@SuppressWarnings("unchecked")
TidalFlow(int NN) {
N=(t=(s=NN)+1)+1;
adj = new ArrayList[N];
for(int i = 0; i < N; adj[i++] = new ArrayList<Edge>());
dist = new int[N];
pool = new int[N];
q = new int[N];
}
void add(int i, int j, int cap) {
Edge fwd = new Edge(i, j, cap, 0);
Edge rev = new Edge(j, i, 0, 0);
adj[i].add(rev.rev=fwd);
adj[j].add(fwd.rev=rev);
}
int augment() {
Arrays.fill(dist, Integer.MAX_VALUE);
pool[t] = dist[s] = fptr = bptr = 0;
pool[q[bptr++] = s] = oo;
while(bptr > fptr && q[fptr] != t)
for(Edge e : adj[q[fptr++]]) {
if(dist[e.i] < dist[e.j])
pool[e.j] += e.carry = Math.min(e.cap - e.flow, pool[e.i]);
if(dist[e.i] + 1 < dist[e.j] && e.cap > e.flow)
dist[q[bptr++] = e.j] = dist[e.i] + 1;
}
if(pool[t] == 0) return 0;
Arrays.fill(pool, fptr = bptr = 0);
pool[q[bptr++] = t] = oo;
while(bptr > fptr)
for(Edge e : adj[q[fptr++]]) {
if(pool[e.i] == 0) break;
int f = e.rev.carry = Math.min(pool[e.i], e.rev.carry);
if(dist[e.i] > dist[e.j] && f != 0) {
if(pool[e.j] == 0) q[bptr++] = e.j;
pool[e.i] -= f;
pool[e.j] += f;
stk.push(e.rev);
}
}
int res = pool[s];
Arrays.fill(pool, 0);
pool[s] = res;
while(stk.size() > 0) {
Edge e = stk.pop();
int f = Math.min(e.carry, pool[e.i]);
pool[e.i] -= f;
pool[e.j] += f;
e.flow += f;
e.rev.flow -= f;
}
return res;
}
int getFlow() {
int res = 0, f = 1;
while(f != 0)
res += f = augment();
return res;
}
class Edge {
int i, j, cap, flow, carry;
Edge rev;
Edge(int ii, int jj, int cc, int ff) {
i=ii; j=jj; cap=cc; flow=ff;
}
}
}
public static class input {
static BufferedReader reader;
static StringTokenizer tokenizer;
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens())
tokenizer = new StringTokenizer(reader.readLine());
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
Python 3 Real Estate Broker HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
def kuhn(v):
global house, used, buyers
if used[v]:
return False
used[v] = True
for buyer in buyers[v]:
if (house[buyer] == -1 or kuhn(house[buyer])):
house[buyer] = v
return True
return False
############################################
sys.setrecursionlimit(30000)
n, m = map(int, input().strip().split())
#clients (n)
a = []
p = []
for i in range(n):
q, w = map(int, input().strip().split())
a.append(q)
p.append(w)
#houses (m)
buyers = [[] for i in range(m)]
for i in range(m):
x, y = map(int, input().strip().split())
for j in range(n):
if x > a[j] and y <= p[j]:
buyers[i].append(j)
#########################################
house = [-1] * (n)
for i in range(m):
used = [False] * (m)
kuhn(i)
res = 0
for h in house:
if (h >= 0):
res += 1
print(res)
C Real Estate Broker HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
void trace(int*edge_left,int*edge_right,int*match,int*list_left,int*list_right,int*right_edge_left,int*right_edge_right,int edge_size,int flag,int index,int*break_flag,int*path,int path_idx,int*index_list,int*track,int N);
void sort_a(int*a,int*b,int*c,int size);
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size);
int a[1000],p[1000],x[1000],y[1000];
int main(){
int n,m,i,j,k,edge_size,break_flag,flag;
int *edge_left,*edge_right,*match,*list_left,*list_right,*path,*right_edge_left,*right_edge_right,*index_list,*track;
edge_left=(int*)malloc(1000000*sizeof(int));
edge_right=(int*)malloc(1000000*sizeof(int));
right_edge_left=(int*)malloc(1000000*sizeof(int));
right_edge_right=(int*)malloc(1000000*sizeof(int));
match=(int*)malloc(1000000*sizeof(int));
list_left=(int*)malloc(1000*sizeof(int));
list_right=(int*)malloc(1000*sizeof(int));
path=(int*)malloc(2000*sizeof(int));
track=(int*)malloc(2000*sizeof(int));
index_list=(int*)malloc(1000000*sizeof(int));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d%d",a+i,p+i);
for(i=0;i<m;i++)
scanf("%d%d",x+i,y+i);
for(i=edge_size=flag=0;i<n;i++,flag=0)
for(j=0;j<m;j++)
if(x[j]>a[i] && y[j]<=p[i]){
edge_left[edge_size]=right_edge_left[edge_size]=i;
edge_right[edge_size]=right_edge_right[edge_size]=j;
match[edge_size]=0;
if(flag==0)
list_left[i]=edge_size;
flag=1;
index_list[edge_size]=edge_size;
edge_size++;
}
sort_a(right_edge_right,right_edge_left,index_list,edge_size);
for(j=0;j<edge_size;j++)
if(j==0||right_edge_right[j]!=right_edge_right[j-1])
list_right[right_edge_right[j]]=j;
for(j=0;j<n;j++){
break_flag=0;
for(k=0;k<n+m;k++)
track[k]=0;
trace(edge_left,edge_right,match,list_left,list_right,right_edge_left,right_edge_right,edge_size,0,j,&break_flag,path,0,index_list,track,n);
}
for(j=0,k=0;j<edge_size;j++)
if(match[j])
k++;
printf("%d",k);
return 0;
}
void trace(int*edge_left,int*edge_right,int*match,int*list_left,int*list_right,int*right_edge_left,int*right_edge_right,int edge_size,int flag,int index,int*break_flag,int*path,int path_idx,int*index_list,int*track,int N){
int i,j,k;
if(flag==0){
if(track[index])
return;
track[index]=1;
j=0;
for(i=list_left[index];i>=0&&i<edge_size&&edge_left[i]==index&&(*break_flag)==0;i++)
if(match[i]==0){
j=1;
path[path_idx]=index;
trace(edge_left,edge_right,match,list_left,list_right,right_edge_left,right_edge_right,edge_size,1,edge_right[i],break_flag,path,path_idx+1,index_list,track,N);
}
if(j==0)
return;
}
else{
if(track[index+N])
return;
track[index+N]=1;
j=0;
for(i=list_right[index];i>=0&&i<edge_size&&right_edge_right[i]==index&&(*break_flag)==0;i++)
if(match[index_list[i]]==1){
j=1;
path[path_idx]=index;
trace(edge_left,edge_right,match,list_left,list_right,right_edge_left,right_edge_right,edge_size,0,right_edge_left[i],break_flag,path,path_idx+1,index_list,track,N);
}
if(j==0){
path[path_idx]=index;
for(i=0;i<path_idx;i++)
if(i%2==0){
for(k=list_left[path[i]];k>=0&&k<edge_size&&edge_left[k]==path[i];k++)
if(match[k]==0&&edge_right[k]==path[i+1])
match[k]=1;
}
else{
for(k=list_right[path[i]];k>=0&&k<edge_size&&right_edge_right[k]==path[i];k++)
if(match[index_list[k]]==1&&right_edge_left[k]==path[i+1])
match[index_list[k]]=0;
}
(*break_flag)=1;
}
}
return;
}
void sort_a(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a(left_a,left_b,left_c,m);
sort_a(right_a,right_b,right_c,size-m);
merge(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
Leave a comment below
