UVa 1237 - Expert Enough?

// UVa 1237 - Expert Enough?

import java.util.*;

public class Main {

    public static void main(String[] args) {

        try (Scanner scanner = new Scanner(System.in)) {
            int cases = scanner.nextInt();
            for (int caseNumber = 1; caseNumber <= cases; caseNumber++) {

                int numberOfIntervals = scanner.nextInt();
                Collection<Interval> intervals = new ArrayList<>();
                for (int i = 0; i < numberOfIntervals; i++) {
                    String maker = scanner.next();
                    Interval<String> interval = new Interval<>(scanner.nextInt(), scanner.nextInt());
                    interval.data = maker;
                    intervals.add(interval);
                }
                IntervalNode intervalTree = IntervalNode.buildFor(intervals);


                int numberOfPoints = scanner.nextInt();
                for (int i = 0; i < numberOfPoints; i++) {
                    int point = scanner.nextInt();
                    Collection<Interval> intersectingIntervals = intervalTree.getIntersectingIntervals(point);
                    if (intersectingIntervals.size() != 1)
                        System.out.println("UNDETERMINED");
                    else
                        System.out.println(intersectingIntervals.iterator().next().data);
                }

                if (caseNumber < cases)
                    System.out.println();
            }
        }

    }

    public static class Interval<D> {

        public int start;
        public int end;
        public D data;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public static Comparator<Interval> COMPARATOR_BY_START = Comparator.comparingInt(i -> i.start);
        public static Comparator<Interval> COMPARATOR_BY_END = Comparator.comparingInt(i -> i.end);

    }


    public static class IntervalNode {

        private int midPoint;
        private IntervalNode left, right;
        private SortedSet<Interval> intervalsByStart = new TreeSet<>(Interval.COMPARATOR_BY_START);
        private SortedSet<Interval> intervalsByEnd = new TreeSet<>(Interval.COMPARATOR_BY_END);

        private IntervalNode(Collection<Interval> intervals) {

            int minStart = Integer.MAX_VALUE;
            int maxEnd = Integer.MIN_VALUE;
            for (Interval interval : intervals) {
                if (interval.start < minStart) minStart = interval.start;
                if (interval.end > maxEnd) maxEnd = interval.end;
            }
            midPoint = (minStart + maxEnd) / 2;

            Collection<Interval> leftIntervals = new ArrayList<>();
            Collection<Interval> rightIntervals = new ArrayList<>();
            for (Interval interval : intervals) {
                if (interval.end < midPoint)
                    leftIntervals.add(interval);
                else if (interval.start > midPoint)
                    rightIntervals.add(interval);
                else {
                    intervalsByStart.add(interval);
                    intervalsByEnd.add(interval);
                }
            }

            left = buildFor(leftIntervals);
            right = buildFor(rightIntervals);

        }

        public static IntervalNode buildFor(Collection<Interval> intervals) {
            if (intervals == null || intervals.isEmpty()) return null;
            return new IntervalNode(intervals);
        }

        public Collection<Interval> getIntersectingIntervals(int point) {
            if (point == midPoint)
                return new ArrayList<>(intervalsByStart);
            else if (point < midPoint) {
                Collection<Interval> intersectingIntervals = new ArrayList<>();
                if (left != null)
                    intersectingIntervals.addAll(left.getIntersectingIntervals(point));
                intersectingIntervals.addAll(intervalsByStart.headSet(new Interval(point + 1, point + 1)));
                return intersectingIntervals;
            } else {
                Collection<Interval> intersectingIntervals = new ArrayList<>();
                if (right != null)
                    intersectingIntervals.addAll(right.getIntersectingIntervals(point));
                intersectingIntervals.addAll(intervalsByEnd.tailSet(new Interval(point, point)));
                return intersectingIntervals;
            }
        }


    }

}