{"id":3529,"date":"2018-08-15T08:05:13","date_gmt":"2018-08-15T15:05:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3529"},"modified":"2018-08-15T08:06:15","modified_gmt":"2018-08-15T15:06:15","slug":"leetcode-455-assign-cookies","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-455-assign-cookies\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 455. Assign Cookies"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"LeetCode 455. Assign Cookies \u82b1\u82b1\u9171 \u5237\u9898\u627e\u5de5\u4f5c EP4\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/3kJpg7Smc3E?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g<sub>i<\/sub>, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s<sub>j<\/sub>. If s<sub>j<\/sub>\u00a0&gt;= g<sub>i<\/sub>, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.<\/p>\n<p><b>Note:<\/b><br \/>\nYou may assume the greed factor is always positive.<br \/>\nYou cannot assign more than one cookie to one child.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> [1,2,3], [1,1]\r\n\r\n<b>Output:<\/b> 1\r\n\r\n<b>Explanation:<\/b> You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. \r\nAnd even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.\r\nYou need to output 1.\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> [1,2], [1,2,3]\r\n\r\n<b>Output:<\/b> 2\r\n\r\n<b>Explanation:<\/b> You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. \r\nYou have 3 cookies and their sizes are big enough to gratify all of the children, \r\nYou need to output 2.\r\n<\/pre>\n<h1>Solution: Greedy + Two Pointers<\/h1>\n<p>Time complexity: O(mlogm + nlogn)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 28 ms\r\nclass Solution {\r\npublic:\r\n  int findContentChildren(vector&lt;int&gt;&amp; g, vector&lt;int&gt;&amp; s) {\r\n    sort(begin(g), end(g));\r\n    sort(begin(s), end(s));\r\n\r\n    int ans = 0;\r\n    int j = 0;\r\n    for (int i = 0; i &lt; g.size(); ++i) { \r\n      while (j &lt; s.size() &amp;&amp; s[j] &lt; g[i]) {\r\n        ++j;\r\n      }\r\n      if (j &lt; s.size()) {\r\n        ++ans;\r\n        ++j;\r\n        continue;\r\n      }\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51,176],"tags":[222,88,377,175],"class_list":["post-3529","post","type-post","status-publish","format-standard","hentry","category-greedy","category-two-pointers","tag-easy","tag-greedy","tag-onlogn","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3529","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3529"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3529\/revisions"}],"predecessor-version":[{"id":3531,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3529\/revisions\/3531"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}