Problem Description: In a Super market we will find many variations of the same product. In the same way we can find many types of rice bags which differ in its quantity, price, brand, and type of rice in it.
Many variations of same products exist in a super market. Consider rice for example. We get it in varying quantities (q) and at different prices (p).
Thus rice bag is unique combination of {q,p}. Customers want to buy the rice bags of their own choices. Each bag has two attributes price and the quantity of rice. The customers have some conditions for buying the rice bags, they have a specific price and quantity that have to be compared with the rice bags before buying them. If the price of rice bag is less than or equal to the customer’s preference and if the quantity is more than given preference, then he/she will buy it. There is only one bag of each type and each customer can buy at most one bag.
Given n,m representing the number of customers and rice bags respectively, along with the variations of rice bags available in the market and the preferences of customers, find the maximum number of bags that can be sold by the end of the day.
Constraints
1 <= n, m <= 1000
1 <= a, b <= 10^5
1 <=p, q<= 10^5
Input
The first line contains two space separated integers n and m denoting the number of customers and number of rice bags respectively.
Next n lines consist of two space separated integers a and b denoting customer’s preferences viz. customer’s quantity and cost preferences, respectively.
Lastly, the next m lines consist of two space separated integers q and p denoting the bags quantity and cost, respectively.
Output
Print the maximum number of rice bags that can be sold.
Time Limit (secs)
1
Examples
Example 1
Input
5 4
35 2400
70 5500
87 6000
20 1700
12 500
50 2500
75 4875
100 7000
25 1250
Output
2
Explanation
Since price of bag should be less than or equal to customer’s preference and the quantity should be greater than the preferred quantity, customer 2 can buy bag 2 and customer 4 can buy bag 4.
So, in total, 2 bags can be sold to the customers.
Example 2
4 7
32 1500
58 5000
87 6200
45 3000
20 1200
60 4500
100 6000
80 5500
35 1400
40 2000
50 2800
Output
4
Explanation
Since price of bag should be less than or equal to customer’s preference and the quantity should be greater than the preferred quantity, customer 1 can buy bag 5, customer 2 can buy bag 2, customer 3 can buy bag 3 and customer 4 can buy 7th bag.
So, in total, 4 bags can be sold to the customers.
Solution in C:
#include <stdio.h>
// Function to find the maximum number of bags that can be sold
int maxBagsSold(int customers[][2], int bags[][2], int n, int m) {
int maxBags = 0;
for (int i = 0; i < n; i++) {
int customerQuantity = customers[i][0];
int customerPrice = customers[i][1];
for (int j = 0; j < m; j++) {
int bagQuantity = bags[j][0];
int bagPrice = bags[j][1];
if (bagPrice <= customerPrice && bagQuantity >= customerQuantity) {
maxBags++;
break;
}
}
}
return maxBags;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int customers[n][2];
for (int i = 0; i < n; i++) {
scanf("%d %d", &customers[i][0], &customers[i][1]);
}
int bags[m][2];
for (int i = 0; i < m; i++) {
scanf("%d %d", &bags[i][0], &bags[i][1]);
}
int maxBags = maxBagsSold(customers, bags, n, m);
printf("%d\n", maxBags);
return 0;
}
You can also run it on an online IDE:
https://ide.geeksforgeeks.org/online-c-compiler/fc646307-f362-4f36-b062-9b1ebe8c9bc3