Assign Cookies

Greedy Algorithms Easy Easy

Consider a scenario where a teacher wants to distribute cookies to students, with each student receiving at most one cookie.


Given two arrays, Student and Cookie, the ith value in the Student array describes the minimum size of cookie that the ith student can be assigned. The jth value in the Cookie array represents the size of the jth cookie. If Cookie[j] >= Student[i], the jth cookie can be assigned to the ith student. Maximize the number of students assigned with cookies and output the maximum number.

Examples:

Input : Student = [1, 2, 3] , Cookie = [1, 1]

Output :1

Explanation : You have 3 students and 2 cookies.

The minimum size of cookies required for students are 1 , 2 ,3.

You have 2 cookies both of size 1, So you can assign the cookie only to student having minimum cookie size 1.

So your answer is 1.

Input : Student = [1, 2] , Cookie = [1, 2, 3]

Output : 2

Explanation : You have 2 students and 3 cookies.

The minimum size of cookies required for students are 1 , 2.

You have 3 cookies and their sizes are big enough to assign cookies to all students.

So your answer is 2.

Input : Student = [4, 5, 1] , Cookie = [6, 4, 2]

Constraints

  • 1 <= Student.length <= 3*104
  • 0 <= Cookie.length <= 3*104
  • 1 <= Student[i] , Cookie[j] <= 231 - 1

Hints

  • Use one pointer to traverse the Student array and another to traverse the Cookie array. If the current cookie satisfies the current student (i.e., Cookie[j] >= Student[i]), assign the cookie to the student and move both pointers forward.
  • The goal is to assign the smallest cookie possible to each student that can satisfy their requirement. This greedy approach minimizes wasted resources and ensures that more students can be assigned cookies.

Company Tags

McKinsey & Company Rakuten Roche Seagate Technology Zoho Flipkart Robinhood Deloitte JPMorgan Chase Oracle Siemens Healthineers Riot Games PwC AMD Wayfair Broadcom Unity Technologies Zynga Visa ARM Freshworks Cloudflare Texas Instruments Shopify Ernst & Young Google Microsoft Amazon Meta Apple Netflix Adobe