刷题第二天

第二天"/>

刷题第二天

前言：这种题目放在两年前我可以很快的写出来，现在看着它一脸懵逼，连easy的都写不出来，我佛啦，六个月速度刷题！！！

知识点：贪心（把大问题分成小问题）

题目920(easy)：给数个会议的占用时间，问你这几个会议有没有冲突的。题目链接

思路：按会议开始时间从小到大排序，判断后面会议开始的时间是不是比前一个会议结束的时间提前，如果是说明gg了。

/*** Definition of Interval:* public classs Interval {*     int start, end;*     Interval(int start, int end) {*         this.start = start;*         this.end = end;*     }* }*/public class Solution {/*** @param intervals: an array of meeting time intervals* @return: if a person could attend all meetings*/public boolean canAttendMeetings(List<Interval> intervals) {// Write your code here//sort the start,from low to highCollections.sort(intervals,new Comparator<Interval>(){public int compare(Interval i1, Interval i2){return i1.start - i2.start;}});int preEnd = 0;for(Interval curr:intervals){if(curr.start<preEnd)return false;preEnd = curr.end;}return true;}
}

难点：重写sort（是我太生疏了）

题目919(medium)：给你数个会议起始、终止时间，问你需要几个会议室安排他们？（是920的进阶了）题目链接

思路：按会议开始时间从小到大排序，创建一个List<Integer>代表房间号，里面存储的是此间会议室结束使用的时间。

          针对每个会议，从第一间会议室开始遍历，判断此会议室满不满足，不满足则增加新的会议室。最后size()就是需要的房间数。

/*** Definition of Interval:* public classs Interval {*     int start, end;*     Interval(int start, int end) {*         this.start = start;*         this.end = end;*     }* }*/public class Solution {/*** @param intervals: an array of meeting time intervals* @return: the minimum number of conference rooms required*/public int minMeetingRooms(List<Interval> intervals) {// Write your code hereCollections.sort(intervals,new Comparator<Interval>(){public int compare(Interval i1, Interval i2){return i1.start - i2.start;//返回>0则进行排序，否则不变}});List<Integer> rooms = new ArrayList<Integer>();rooms.add(-1);boolean flag = false;for(Interval ival:intervals){for(int i=0;i<rooms.size();i++){if(ival.start>rooms.get(i)){rooms.set(i,ival.end);flag = true;break;}}if(!flag){rooms.add(ival.end);}flag = false;}return rooms.size();}
}

到此为止，明天继续冲贪心。btw，刷题好累。我的发际线可能又要上移动了。