We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Real Estate Broker

Real Estate Broker

Problem
Submissions
Leaderboard
Discussions
Editorial

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.

Author

nabila_ahmed

Difficulty

Hard

Max Score

60

Submitted By

2721

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy