会议室问题

左手的ㄟ右手 2024-02-18 20:39 48阅读 0赞

### 题目 ###

描述  
给定一系列的会议时间间隔，包括起始和结束时间\[\[s1,e1\]，\[s2,e2\]，…(si < ei)，确定一个人是否可以参加所有会议。

您在真实的面试中是否遇到过这个题？  
样例  
给定区间=\[\[0,30\]，\[5,10\]，\[15,20\]\]，返回false。

### 解答 ###

public class MeetingRooms2 {
        
        public static void main(String[] args) {
            Interval interval1 = new Interval(0, 5);
            Interval interval2 = new Interval(5, 10);
            Interval interval3 = new Interval(15, 20);
            Interval interval4 = new Interval(3, 4);
    
            List<Interval> intervalList = new ArrayList<Interval>();
            intervalList.add(interval1);
            intervalList.add(interval2);
            intervalList.add(interval3);
            intervalList.add(interval4);
            System.out.println(canAttendMeetings(intervalList));
        }
    
        /**
         * @param intervals: an array of meeting time intervals
         * @return: if a person could attend all meetings
         */
        public static boolean canAttendMeetings(List<Interval> intervals) {
            if (intervals.size() == 0) {
                return true;
            }
            // Write your code here
            sortIntervals(intervals);
            int max = intervals.get(0).end;
            for (int i = 1; i < intervals.size(); i++) {
                if (intervals.get(i).start < max) {
                    return false;
                } else {
                    max = intervals.get(i).end;
                }
            }
            return true;
        }
    
        public static void sortIntervals(List<Interval> intervals) {
            Map<String, Interval> intervalMap = new HashMap<String, Interval>();
            for (Interval interval : intervals) {
                intervalMap.put(interval.start + interval.end + "", interval);
            }
    
            for (int i = 0; i < intervals.size(); i++) {
                int minIndex = i;
                for (int j = i; j < intervals.size(); j++) {
                    if (intervals.get(j).start < intervals.get(minIndex).start) {
                        minIndex = j;
                    }
                }
                //交换两个位置
                if (minIndex != i) {
                    Interval interval = intervals.get(i);
                    intervals.set(i, intervals.get(minIndex));
                    intervals.set(minIndex, interval);
                }
            }
            System.out.println(intervals);
        }
    
        static class Interval {
            int start, end;
    
            Interval(int start, int end) {
                this.start = start;
                this.end = end;
            }
        }
    }