Oscar 最新oa, 求solution, GHC 拼住宿

[yilishabaishu (伊丽莎白鼠)]

求apointment schedule 的 solution，另外再问下有没有妹子可以GHC拼住宿

[Xavier]

用 greedy 方法写了一下，不一定能cover所有case。

package oscar;

import java.util.*;

public class AppointmentSchedule {
	
	static class Interval implements Comparable<Interval> {
		
		int s;
		int e;
		int len;

		public Interval(int s, int e) {
			this.s = s;
			this.e = e;
			this.len = e - s + 1;
		}

		@Override
		public int compareTo(Interval o) {
			return Integer.compare(this.len, o.len);
		}
		
		public boolean contains(int d) {
			return this.s <= d && this.e >= d;
		}
		
	}

	static int schedule(int[] s, int[] e) {
		int n = s.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		List<Interval> intervals = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			min = Math.min(min, s[i]);
			max = Math.max(max, e[i]);
			intervals.add(new Interval(s[i], e[i]));
		}
		
		int count = 0;
		for (int i = min; i <= max; i++) {
			Collections.sort(intervals);
			Iterator<Interval> iter = intervals.iterator();
			while (iter.hasNext()) {
				if (iter.next().contains(i)) {
					iter.remove();
					count++;
					break;
				}
			}
			
			if (intervals.isEmpty()) {
				break;
			}
		}
		return count;
	}

	public static void main(String[] args) {
		System.out.println(schedule(new int[] { 1, 2, 3, 3, 3 }, new int[] { 2, 2, 3, 4, 4 }));
	}

}