குக்கீகள் லீட்கோட் தீர்வை ஒதுக்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான்
பேராசை

குக்கீகளை ஒதுக்குவதில் சிக்கல் லீட்கோட் தீர்வு இரண்டு வரிசைகளை வழங்குகிறது. ஒன்று வரிசைகள் குக்கீகளின் அளவைக் குறிக்கிறது, மற்றொன்று குழந்தைகளின் பேராசைகளைக் குறிக்கிறது. நீங்கள் குழந்தைகளின் பெற்றோர் என்று சிக்கல் கூறுகிறது, மேலும் அதிகபட்ச எண்ணிக்கையிலான குழந்தைகள் திருப்தியடைய வேண்டும் என்று நீங்கள் விரும்புகிறீர்கள். நீங்கள் ஒரு குழந்தைக்கு ஒரு குக்கீ மட்டுமே கொடுக்க முடியும். உள்ளடக்க குழந்தைகளின் அதிகபட்ச எண்ணிக்கையைக் கண்டறியவும். முதலில் சில எடுத்துக்காட்டுகளை எடுத்துக்கொள்வோம்.

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (NlogN), கொடுக்கப்பட்ட வரிசைகளை வரிசைப்படுத்த தேவையான நேரம் காரணமாக. இங்கே N கொடுக்கப்பட்ட வரிசைகளில் உள்ள உறுப்புகளின் எண்ணிக்கையைக் குறிக்கிறது.

விண்வெளி சிக்கலானது

ஓ (NlogN), கொடுக்கப்பட்ட வரிசைகளை வரிசைப்படுத்த தேவையான இடம் இருப்பதால். மீண்டும் N என்பது வரிசைகளில் உள்ள உறுப்புகளின் எண்ணிக்கையைக் குறிக்கிறது.