Cerinta completa

You are a real estate broker in ancient Knossos. You have unsold houses, and each house has an area, , and a minimum price, . You also have clients, and each client wants a house with an area greater than and a price less than or equal to .

Each client can buy at most one house, and each house can have at most one owner. What is the maximum number of houses you can sell?

Input Format

The first line contains two space-separated integers describing the respective values of (the number of clients) and (the number of houses).
Each line of the subsequent lines contains two space-separated integers describing the respective values of and for client .
Each line of the subsequent lines contains two space-separated integers describing the respective values of and for house .

Constraints

  • , where .
  • , where .

Output Format

Print a single integer denoting the maximum number of houses you can sell.

Sample Input 0

3 3
5 110
9 500
20 400
10 100
2 200
30 300

Sample Output 0

2

Explanation 0

Recall that each client is only interested in some house where and . The diagram below depicts which clients will be interested in which houses:

image

  • Client will be interested in house because it has more than units of space and costs less than . Both of the other houses are outside of this client’s price range.
  • Client will be interested in houses and , as both these houses have more than units of space and cost less than . They will not be interested in the remaining house because it’s too small.
  • Client will be interested in house because it has more than units of space and costs less than . They will not be interested in the other two houses because they are too small.

All three clients are interested in the same two houses, so you can sell at most two houses in the following scenarios:

  • Client buys house and client buys house .
  • Client buys house and client buys house .
  • Client buys house and client buys house .

Thus, we print the maximum number of houses you can sell, , on a new line.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return sign == 1 ? val : -val;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    static int n, m;
    static int[][] adj;
    static int[] pairU, pairV, dist;

    static boolean bfs() {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        Arrays.fill(dist, -1);
        for (int u = 0; u < n; u++) {
            if (pairU[u] == -1) {
                dist[u] = 0;
                q.add(u);
            }
        }

        boolean found = false;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                int pu = pairV[v];
                if (pu == -1) {
                    found = true;
                } else if (dist[pu] == -1) {
                    dist[pu] = dist[u] + 1;
                    q.add(pu);
                }
            }
        }
        return found;
    }

    static boolean dfs(int u) {
        for (int v : adj[u]) {
            int pu = pairV[v];
            if (pu == -1 || (dist[pu] == dist[u] + 1 && dfs(pu))) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        n = fs.nextInt();
        m = fs.nextInt();

        long[] a = new long[n];
        long[] p = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = fs.nextLong();
            p[i] = fs.nextLong();
        }

        long[] x = new long[m];
        long[] y = new long[m];
        for (int j = 0; j < m; j++) {
            x[j] = fs.nextLong();
            y[j] = fs.nextLong();
        }

        adj = new int[n][];
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < m; j++) {
                if (x[j] > a[i] && y[j] <= p[i]) cnt++;
            }
            int[] row = new int[cnt];
            int t = 0;
            for (int j = 0; j < m; j++) {
                if (x[j] > a[i] && y[j] <= p[i]) row[t++] = j;
            }
            adj[i] = row;
        }

        pairU = new int[n];
        pairV = new int[m];
        dist = new int[n];
        Arrays.fill(pairU, -1);
        Arrays.fill(pairV, -1);

        int match = 0;
        while (bfs()) {
            for (int u = 0; u < n; u++) {
                if (pairU[u] == -1 && dfs(u)) match++;
            }
        }

        System.out.println(match);
    }
}

Scor obtinut: 1.0

Submission ID: 464619912

Link challenge: https://www.hackerrank.com/challenges/real-estate-broker/problem

Real Estate Broker