package com.waze;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author Matan Sabag
 * @date 24/04/2019
 * Answer from test 31053880
 */
public class FirstInteger {

    static class Range {

        long start;
        long end;

        Range(long start, long end) {
            this.start = start;
            this.end = end;
        }
    }

    public static long getFirstNumber(List<Range> ranges) {
        ranges.sort((r1, r2) -> {
            int c = Long.compare(r1.start, r2.start);
            if (c == 0) return Long.compare(r1.end, r2.end);
            return c;
        }); // O(n log n)
        List<Range> merged = mergeRanges(ranges);
        Long candidate = 0L;
        for (int i = 0; i < merged.size(); i++) {
            Range r = merged.get(i);
            if (candidate < r.start) return candidate;
            candidate = r.end + 1;
        }
        return candidate;
    }

    private static List<Range> mergeRanges(List<Range> ranges) {
        ArrayList<Range> list = new ArrayList<>();
        if (ranges == null || ranges.size() == 0) return list;
        list.add(ranges.get(0));
        for (int i = 1; i < ranges.size(); i++) {
            Range r = ranges.get(i);
            if (r.start > list.get(list.size() - 1).end) {
                list.add(r);
            } else {
                Range lastInterval = list.get(list.size() - 1);
                lastInterval.start = Math.min(lastInterval.start, r.start);
                lastInterval.end = Math.max(lastInterval.end, r.end);
            }
        }
        return list;
    }

    public static Range rowToRange(String s) {
        String[] split = s.split("-");
        return new Range(Long.valueOf(split[0]), Long.valueOf(split[1]));
    }

    public static void main(String[] args) {

        String fileName = "C:\\dev\\crack\\src\\com\\waze\\test.txt";
        List<Range> list;

        try (Stream<String> stream = Files.lines(Paths.get(fileName))) {

            list = stream
                    .map(FirstInteger::rowToRange)
                    .collect(Collectors.toCollection(ArrayList::new));
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }
        System.out.println(getFirstNumber(list));
    }
}