455. 分發(fā)餅干
假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。對每個孩子 i ，都有一個胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個尺寸 sj 。如果 sj >= gi ，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。
注意：
你可以假設(shè)胃口值為正。
一個小朋友最多只能擁有一塊餅干。
示例 1:
輸入: [1,2,3], [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
</pre>
示例 2:
輸入: [1,2], [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.</pre>
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);//貪心算法中大多都和排序有關(guān)，要先排序
Arrays.sort(s);
int si=0;
int gi=0;
int res=0;
while(gi<g.length&&si<s.length)
{if(s[si]>=g[gi]){
res++;
si++;
gi++;
} else
si++;
}
return res;
}
}
貪心和動態(tài)規(guī)劃的關(guān)系
435. 無重疊區(qū)間
給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。
注意:
- 可以認(rèn)為區(qū)間的終點總是大于它的起點。
- 區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。
示例 1:
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。
示例 2:
輸入: [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區(qū)間沒有重疊。
</pre>
示例 3:
輸入: [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了。
public class Solution {
class myComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
public boolean isOverlapping(Interval i, Interval j) {
return i.end > j.start;
}
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new myComparator());
int dp[] = new int[intervals.length];
dp[0] = 1;
int ans = 1;
for (int i = 1; i < dp.length; i++) {
int max = 0;
for (int j = i - 1; j >= 0; j--) {
if (!isOverlapping(intervals[j], intervals[i])) {
max = Math.max(dp[j], max);
}
}
dp[i] = max + 1;
ans = Math.max(ans, dp[i]);
}
return intervals.length - ans;
}
}
作者：LeetCode
鏈接：https://leetcode-cn.com/problems/non-overlapping-intervals/solution/wu-zhong-die-qu-jian-by-leetcode/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
