## DEV Community is a community of 665,273 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# [DataStructure&Algorithm] 1. Greedy Nina Hwang
👩🏻‍💻 황채영 🐣 Junior Backend Developer

# 1. Greedy Algorithms

Greedy algorithm is an algorithm that makes the optimal choice at each step. Since it only makes decisions based on the information it has at each step and does not care about the overall information, it may not produce an optimal solution.

# 2. Problem Solutions

``````# python

class Solution:
vowels = ['a', 'e', 'i', 'o', 'u']
vowel_cnt, consonant_cnt = 0, 0

for char in S:
if char == '?':
vowel_cnt += 1
consonant_cnt += 1
elif char in vowels:
vowel_cnt += 1
consonant_cnt = 0
else:
vowel_cnt = 0
consonant_cnt += 1

if vowel_cnt > 5 or consonant_cnt > 3:
return 0
return 1

# Execution Time:0.03
``````
``````//java

class Solution {
char[] vowels = {'a', 'e', 'i', 'o', 'u'};
int vowel_cnt = 0;
int consonant_cnt = 0;

for (char ch: S.toCharArray()) {
boolean is_vowel = false;
if (ch == '?'){
vowel_cnt++;
consonant_cnt++;
}else{
for (char vowel: vowels) {
if (vowel == ch) {
is_vowel = true;
break;
}
}
if (is_vowel==true) {
vowel_cnt++;
consonant_cnt = 0;
}else{
vowel_cnt = 0;
consonant_cnt++;
}
}
if (vowel_cnt > 5 || consonant_cnt > 3){
return 0;
}
}
return 1;
}
};

// Execution Time:0.23
``````

### Majority Element

``````# python

class Solution:
def majorityElement(self, A, N):
half = len(A) / 2
A.sort()
n = 0
for i in A:
if n != i:
n = i
majority = 1
else:
majority += 1
if majority > half:
return i
return -1

# Execution Time:1.17
``````
``````//java

class Solution
{
static int majorityElement(int a[], int size)
{
Arrays.sort(a);
int n = 0;
int half = a.length / 2;
int majority = 0;
for (int i: a){
if (i != n) {
n = i;
majority = 1;
} else {
majority++;
}

if (majority > half) {
return i;
}
}
return -1;
}
}

// Execution Time:3.14
``````

### Maximize Toys

``````# python

class Solution:
def toyCount(self, N, K, arr):
arr.sort()
for cost in arr:
if cost + total <= K:
total += cost
else:
break

# Execution Time:0.61
``````
``````// java

class Solution{
static int toyCount(int N, int K, int arr[])
{
// code here
Arrays.sort(arr);
int total = 0;

for (int cost: arr) {
if (cost + total <= K) {
total += cost;
} else {
break;
}
}
}
}

// Execution Time:1.00
``````

### N Meetings in One Room

``````# python

class Solution:
def maximumMeetings(self,n,start,end):
if n == 1:
return 1

li = []
for i in range(n):
li.append((start[i], end[i]))

li.sort(key=lambda tup: (tup, tup))

cnt = 1
current_meeting = li
for next_meeting in li[1:]:
if current_meeting >= next_meeting:
continue
current_meeting = next_meeting
cnt += 1

return cnt

# Execution Time:1.13
``````
``````//java

class Solution
{
public static int maxMeetings(int start[], int end[], int n)
{
int[][] schedules = new int[n];

for(int i = 0; i < n; i++){
schedules[i] = start[i];
schedules[i] = end[i];
}
Arrays.sort(schedules, Comparator.comparing(arr -> arr));

int cnt = 1;
int[] current_meeting = schedules;
int[][] li = Arrays.copyOfRange(schedules, 1, n);
for (int[] next_meeting: li){
if (current_meeting >= next_meeting) {
continue;
}else {
current_meeting = next_meeting;
cnt++;
}
}
return cnt;
}
}

// Execution Time:2.96
``````

I am a beginner in Java, so I just wrote code in Python and translated it into Java. Maybe that's why the execution times of the Java codes are so long. I should refactor these once I get more familiar with Java.