කුකීස් ලීට්කෝඩ් විසඳුම පවරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන්
කෑදරකම

කුකීස් පැවරීමේ ගැටළුව ලීට්කෝඩ් විසඳුම අරා දෙකක් සපයයි. එකෙකු අරා කුකීස් ප්‍රමාණය නියෝජනය කරන අතර අනෙක දරුවන්ගේ කෑදරකම නියෝජනය කරයි. ගැටලුවේ සඳහන් වන්නේ ඔබ දරුවන්ගේ දෙමව්පියන් වන අතර උපරිම දරුවන් සංඛ්‍යාව සෑහීමකට පත්වීමට ඔබට අවශ්‍ය බවය. ඔබට දරුවෙකුට ලබා දිය හැක්කේ එක් කුකියක් පමණි. අන්තර්ගතයේ උපරිම දරුවන් සංඛ්‍යාව සොයා ගන්න. පළමුව උදාහරණ කිහිපයක් බලමු.

g = [1,2,3], s = [1,1]
1

පැහැදිලි කිරීම: අපට 1 ප්‍රමාණයේ කුකීස් දෙකක් සහ විවිධ අන්තර්ගත අගයන් සහිත දරුවන් තිදෙනෙක් සිටී. අපට කෑදරකමේ වටිනාකමක් ඇති තනි ළමා අන්තර්ගතයක් පමණක් සෑදිය හැකිය 1. අනෙක් දරුවන් දෙදෙනාට විශාල කුකීස් අවශ්‍ය බැවින්.

කුකීස් ලීට්කෝඩ් විසඳුම පවරන්න

g = [1,2], s = [1,2,3]
2

පැහැදිලි කිරීම: අපට ඇති කුකීස් අවශ්‍ය ප්‍රමාණයට වඩා වැඩි හෝ සමාන බැවින් අපට දරුවන් දෙදෙනාට සෑහීමකට පත්විය හැකිය. මේ අනුව ප්‍රතිදානය 2 කි.

කුකීස් ලීට්කෝඩ් විසඳුම පැවරීම සඳහා ප්‍රවේශය

කුකීස් ලීට්කෝඩ් විසඳුම පැවරීමේ ගැටලුව අපෙන් ඉල්ලා සිටින්නේ අපට දරුවෙකුට එක් කුකියක් පමණක් ලබා දිය හැකි නම් උපරිම අන්තර්ගත දරුවන් සංඛ්‍යාව සොයා ගන්නා ලෙසයි. මේ අනුව හොඳම ප්‍රවේශය නම්, කෑදරකමින් අවම කෑදර දරුවාට භාවිතා කළ හැකි කුඩාම කුකී සමඟ සෑහීමකට පත්වීමට උත්සාහ කිරීමයි. එබැවින්, මෙම ක්‍රියාවලිය අනුකරණය කිරීම සඳහා අපි ලබා දී ඇති අරා දෙකම වර්ග කර කුකීස් දරුවන්ට පැවරීමට උත්සාහ කරමු. අපට වත්මන් කුකිය වත්මන් දරුවාට පැවරිය නොහැකි නම්, අපි වත්මන් දරුවා තෘප්තිමත් කරන තෙක් ඊළඟ කුකිය උත්සාහ කරමු. මොකද අපට වත්මන් දරුවා තෘප්තිමත් කළ නොහැකි නම්, වත්මන් කුකිය සමඟ ඊළඟ දරුවන් තෘප්තිමත් කළ නොහැක.

කේතය

කුකීස් ලීට්කෝඩ් විසඳුම පැවරීම සඳහා සී ++ කේතය

#include <bits/stdc++.h>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int numberOfChildren = g.size(), numberOfCookies = s.size();
    int cookie = 0, answer = 0;
    for(int i=0;i<numberOfChildren && cookie<numberOfCookies;){
        if(s[cookie] >= g[i]){
            i++;
            answer++;
        }
        cookie++;
    }
    return answer;
}

int main(){
    vector<int> g = {1, 2, 3};
    vector<int> s = {1, 1};

    cout<<findContentChildren(g, s);
}
1

කුකීස් ලීට්කෝඩ් විසඳුම පැවරීම සඳහා ජාවා කේතය

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numberOfChildren = g.length;
        int numberOfCookies = s.length;
        int cookie = 0, answer = 0;
        for(int i=0;i<numberOfChildren && cookie<numberOfCookies;){
            if(s[cookie] >= g[i]){
                i++;
                answer++;
            }
            cookie++;
        }
        return answer;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] g = {1, 2, 3};
    int[] s = {1, 1};
 
    System.out.println(findContentChildren(g, s));
  }
}
1

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (NlogN), දී ඇති අරා වර්ග කිරීමට ගතවන කාලය නිසා. මෙහි N නිරූපණය කර ඇති අරා වල මූලද්‍රව්‍ය ගණන නියෝජනය කරයි.

අභ්‍යවකාශ සංකීර්ණතාව

O (NlogN), දී ඇති අරා වර්ග කිරීමට අවශ්‍ය ඉඩ ප්‍රමාණය නිසා. නැවතත් N නිරූපණය කරන්නේ අරා වල ඇති මූලද්‍රව්‍ය ගණනයි.