탐욕스러운
한 방에서 N 회의
Tc: O(NlogN) as we are using MinHeap(PriorityQueue)
class Solution
{
//Function to find the maximum number of meetings that can
//be performed in a meeting room.
public static int maxMeetings(int start[], int end[], int n)
{
// add your code here
PriorityQueue<MData> q = new PriorityQueue<>((a,b)-> a.getEnd()-b.getEnd());
for(int i =0;i<start.length;i++){
q.add(new MData(start[i],end[i],i));
}
int count =0;
int ps = -1,pe = -1;
while(!q.isEmpty()){
MData m = q.remove();
if(m.getStart() > pe){
count ++;
ps = m.getStart();
pe = m.getEnd();
}
}
return count;
}
}
class MData{
int start;
int end;
int index;
public MData(int s,int e,int i){
this.start = s;
this.end = e;
this.index =i;
}
public int getEnd(){
return this.end;
}
public int getStart(){
return this.start;
}
public int getIndex(){
return this.index;
}
}
작업 시퀀싱 문제
TC: O(nlogn)
class Solution
{
//Function to find the maximum profit and the number of jobs done.
int[] JobScheduling(Job arr[], int n)
{
// Your code here
int maxDeadline = 0;
for(int i =0;i<arr.length;i++){
maxDeadline = Integer.max(maxDeadline, arr[i].deadline);
}
int slots[] = new int[maxDeadline];
HashSet<Integer> set = new HashSet<>();
int result[] = new int[2];
Arrays.fill(slots,-1);//none of the slots are occupied
Arrays.sort(arr,new Comparator<Job>(){
public int compare(Job a, Job b){
return b.profit-a.profit;
}
});
// for(int i =0;i<arr.length;i++)
// System.out.println(arr[i].deadline);
int maxJobs = 0;
int maxProfit =0;
for(int i =0;i<arr.length;i++){
int j = arr[i].deadline-1;// we will try to put the job at its deadline
// if that slot is already occupied by some other jobId then we will decrement
// the index to see if the ith job can be placed on earlier slots or not
while(j>=0 && slots[j] !=-1){
j--;
}
//now while loop has exited it can mean only two things
//either we have found a slot(with index>=0) whose value is -1 (meaning ith job can be place here)
//or we all the index of the slots from jth to 0th are occupied by other job ids hence
//we won't be considering this job as it can't be scheduled
if(j>=0){
maxProfit+=arr[i].profit;
maxJobs++;
slots[j] = arr[i].id; // jth slot is occupied by ith job
}
}
return new int[]{maxJobs,maxProfit};
}
}
/*
class Job {
int id, profit, deadline;
Job(int x, int y, int z){
this.id = x;
this.deadline = y;
this.profit = z;
}
}
*/
최소 플랫폼
TC: O(nlogn)
//User function Template for Java
class Solution
{
//Function to find the minimum number of platforms required at the
//railway station such that no train waits.
static int findPlatform(int arr[], int dep[], int n)
{
// add your code here
Arrays.sort(arr);
Arrays.sort(dep);
int i =0,j=0;
int result = 0;
int currentPlat =0;
while(i<arr.length && j< dep.length){
if(arr[i]<=dep[j]){
i++;
currentPlat++;
}
else if(arr[i] > dep[j]){
j++;
currentPlat--;
}
result = Integer.max(result,currentPlat);
}
return result;
}
}
탐욕을 사용하는 분수 배낭
TC : O(nlogn)
/*
class Item {
int value, weight;
Item(int x, int y){
this.value = x;
this.weight = y;
}
}
*/
class Solution
{
//Function to get the maximum total value in the knapsack.
double fractionalKnapsack(int W, Item arr[], int n)
{
Arrays.sort(arr,new Comparator<Item>(){
public int compare(Item a, Item b){
double aa =(double)a.value/(double)a.weight;
double bb = (double)b.value/(double)b.weight;
return aa > bb ? -1 : 1;
}
});
double result =0.0;
int currentW = 0;
for(Item i : arr){
if(W>=i.weight+currentW){
currentW+=i.weight;
result+= i.value;
}
else{
int remain = W-currentW;
result+= ((double)i.value / (double)i.weight) * (double)remain;
break;
}
}
return result;
}
}
동전의 수
Tc: O(N*M) where N is no of coins and M is target or amount
class Solution{
public int minCoins(int coins[], int M, int V)
{
// Your code goes here
int dp[][] = new int[M][V+1];
for(int row[] : dp) Arrays.fill(row,-1);
int result = getCoins(M-1,coins,V,dp);
return result==1000000 ? -1 : result ;
}
public int getCoins(int index,int[] coins,int target,int dp[][]){
if(index==0){
if(target % coins[index]== 0) return target/coins[index];
return 1000000;
}
if(dp[index][target]!=-1) return dp[index][target];
int take = 1000000;
if(coins[index]<=target){
take = 1 + getCoins(index,coins,target-coins[index],dp);
}
int dontTake = 0 + getCoins(index-1,coins,target,dp);
return dp[index][target] = Integer.min(take,dontTake);
}
}
Reference
이 문제에 관하여(탐욕스러운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/prashantrmishra/greedy-166h
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
class Solution
{
//Function to find the maximum number of meetings that can
//be performed in a meeting room.
public static int maxMeetings(int start[], int end[], int n)
{
// add your code here
PriorityQueue<MData> q = new PriorityQueue<>((a,b)-> a.getEnd()-b.getEnd());
for(int i =0;i<start.length;i++){
q.add(new MData(start[i],end[i],i));
}
int count =0;
int ps = -1,pe = -1;
while(!q.isEmpty()){
MData m = q.remove();
if(m.getStart() > pe){
count ++;
ps = m.getStart();
pe = m.getEnd();
}
}
return count;
}
}
class MData{
int start;
int end;
int index;
public MData(int s,int e,int i){
this.start = s;
this.end = e;
this.index =i;
}
public int getEnd(){
return this.end;
}
public int getStart(){
return this.start;
}
public int getIndex(){
return this.index;
}
}
TC: O(nlogn)
class Solution
{
//Function to find the maximum profit and the number of jobs done.
int[] JobScheduling(Job arr[], int n)
{
// Your code here
int maxDeadline = 0;
for(int i =0;i<arr.length;i++){
maxDeadline = Integer.max(maxDeadline, arr[i].deadline);
}
int slots[] = new int[maxDeadline];
HashSet<Integer> set = new HashSet<>();
int result[] = new int[2];
Arrays.fill(slots,-1);//none of the slots are occupied
Arrays.sort(arr,new Comparator<Job>(){
public int compare(Job a, Job b){
return b.profit-a.profit;
}
});
// for(int i =0;i<arr.length;i++)
// System.out.println(arr[i].deadline);
int maxJobs = 0;
int maxProfit =0;
for(int i =0;i<arr.length;i++){
int j = arr[i].deadline-1;// we will try to put the job at its deadline
// if that slot is already occupied by some other jobId then we will decrement
// the index to see if the ith job can be placed on earlier slots or not
while(j>=0 && slots[j] !=-1){
j--;
}
//now while loop has exited it can mean only two things
//either we have found a slot(with index>=0) whose value is -1 (meaning ith job can be place here)
//or we all the index of the slots from jth to 0th are occupied by other job ids hence
//we won't be considering this job as it can't be scheduled
if(j>=0){
maxProfit+=arr[i].profit;
maxJobs++;
slots[j] = arr[i].id; // jth slot is occupied by ith job
}
}
return new int[]{maxJobs,maxProfit};
}
}
/*
class Job {
int id, profit, deadline;
Job(int x, int y, int z){
this.id = x;
this.deadline = y;
this.profit = z;
}
}
*/
최소 플랫폼
TC: O(nlogn)
//User function Template for Java
class Solution
{
//Function to find the minimum number of platforms required at the
//railway station such that no train waits.
static int findPlatform(int arr[], int dep[], int n)
{
// add your code here
Arrays.sort(arr);
Arrays.sort(dep);
int i =0,j=0;
int result = 0;
int currentPlat =0;
while(i<arr.length && j< dep.length){
if(arr[i]<=dep[j]){
i++;
currentPlat++;
}
else if(arr[i] > dep[j]){
j++;
currentPlat--;
}
result = Integer.max(result,currentPlat);
}
return result;
}
}
탐욕을 사용하는 분수 배낭
TC : O(nlogn)
/*
class Item {
int value, weight;
Item(int x, int y){
this.value = x;
this.weight = y;
}
}
*/
class Solution
{
//Function to get the maximum total value in the knapsack.
double fractionalKnapsack(int W, Item arr[], int n)
{
Arrays.sort(arr,new Comparator<Item>(){
public int compare(Item a, Item b){
double aa =(double)a.value/(double)a.weight;
double bb = (double)b.value/(double)b.weight;
return aa > bb ? -1 : 1;
}
});
double result =0.0;
int currentW = 0;
for(Item i : arr){
if(W>=i.weight+currentW){
currentW+=i.weight;
result+= i.value;
}
else{
int remain = W-currentW;
result+= ((double)i.value / (double)i.weight) * (double)remain;
break;
}
}
return result;
}
}
동전의 수
Tc: O(N*M) where N is no of coins and M is target or amount
class Solution{
public int minCoins(int coins[], int M, int V)
{
// Your code goes here
int dp[][] = new int[M][V+1];
for(int row[] : dp) Arrays.fill(row,-1);
int result = getCoins(M-1,coins,V,dp);
return result==1000000 ? -1 : result ;
}
public int getCoins(int index,int[] coins,int target,int dp[][]){
if(index==0){
if(target % coins[index]== 0) return target/coins[index];
return 1000000;
}
if(dp[index][target]!=-1) return dp[index][target];
int take = 1000000;
if(coins[index]<=target){
take = 1 + getCoins(index,coins,target-coins[index],dp);
}
int dontTake = 0 + getCoins(index-1,coins,target,dp);
return dp[index][target] = Integer.min(take,dontTake);
}
}
Reference
이 문제에 관하여(탐욕스러운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/prashantrmishra/greedy-166h
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
//User function Template for Java
class Solution
{
//Function to find the minimum number of platforms required at the
//railway station such that no train waits.
static int findPlatform(int arr[], int dep[], int n)
{
// add your code here
Arrays.sort(arr);
Arrays.sort(dep);
int i =0,j=0;
int result = 0;
int currentPlat =0;
while(i<arr.length && j< dep.length){
if(arr[i]<=dep[j]){
i++;
currentPlat++;
}
else if(arr[i] > dep[j]){
j++;
currentPlat--;
}
result = Integer.max(result,currentPlat);
}
return result;
}
}
TC : O(nlogn)
/*
class Item {
int value, weight;
Item(int x, int y){
this.value = x;
this.weight = y;
}
}
*/
class Solution
{
//Function to get the maximum total value in the knapsack.
double fractionalKnapsack(int W, Item arr[], int n)
{
Arrays.sort(arr,new Comparator<Item>(){
public int compare(Item a, Item b){
double aa =(double)a.value/(double)a.weight;
double bb = (double)b.value/(double)b.weight;
return aa > bb ? -1 : 1;
}
});
double result =0.0;
int currentW = 0;
for(Item i : arr){
if(W>=i.weight+currentW){
currentW+=i.weight;
result+= i.value;
}
else{
int remain = W-currentW;
result+= ((double)i.value / (double)i.weight) * (double)remain;
break;
}
}
return result;
}
}
동전의 수
Tc: O(N*M) where N is no of coins and M is target or amount
class Solution{
public int minCoins(int coins[], int M, int V)
{
// Your code goes here
int dp[][] = new int[M][V+1];
for(int row[] : dp) Arrays.fill(row,-1);
int result = getCoins(M-1,coins,V,dp);
return result==1000000 ? -1 : result ;
}
public int getCoins(int index,int[] coins,int target,int dp[][]){
if(index==0){
if(target % coins[index]== 0) return target/coins[index];
return 1000000;
}
if(dp[index][target]!=-1) return dp[index][target];
int take = 1000000;
if(coins[index]<=target){
take = 1 + getCoins(index,coins,target-coins[index],dp);
}
int dontTake = 0 + getCoins(index-1,coins,target,dp);
return dp[index][target] = Integer.min(take,dontTake);
}
}
Reference
이 문제에 관하여(탐욕스러운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/prashantrmishra/greedy-166h
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
class Solution{
public int minCoins(int coins[], int M, int V)
{
// Your code goes here
int dp[][] = new int[M][V+1];
for(int row[] : dp) Arrays.fill(row,-1);
int result = getCoins(M-1,coins,V,dp);
return result==1000000 ? -1 : result ;
}
public int getCoins(int index,int[] coins,int target,int dp[][]){
if(index==0){
if(target % coins[index]== 0) return target/coins[index];
return 1000000;
}
if(dp[index][target]!=-1) return dp[index][target];
int take = 1000000;
if(coins[index]<=target){
take = 1 + getCoins(index,coins,target-coins[index],dp);
}
int dontTake = 0 + getCoins(index-1,coins,target,dp);
return dp[index][target] = Integer.min(take,dontTake);
}
}
Reference
이 문제에 관하여(탐욕스러운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/greedy-166h텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)