package com.geeksforgeeks.stacks;

import com.geeksforgeeks.LinkedList.PairWiseSwap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Created by Vaidehi Murarka on 2/8/2017.
 * https://leetcode.com/problems/merge-intervals/
 */
public class MergeIntervals {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals == null || intervals.size() == 0 || intervals.size() == 1){
            return intervals;
        }

        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start < o2.start){
                    return -1;
                } else {
                    if(o1.start > o2.start){
                        return 1;
                    } else {
                        if(o1.end < o2.end){
                            return -1;
                        } else {
                            if(o1.end > o2.end){
                                return 1;
                            } else {
                                return 0;
                            }
                        }
                    }
                }
            }
        });

        List<Interval> result = new ArrayList<>();
        int topStart = intervals.get(0).start;
        int topEnd = intervals.get(0).end;
        for(int index = 1; index < intervals.size(); index++){
            Interval currentI = intervals.get(index);
            /*
                When a conflict
             */
            if(currentI.start >= topStart && currentI.start <= topEnd){
                Interval mergedInterval = new Interval(
                        Math.min(topStart, currentI.start),
                        Math.max(topEnd, currentI.end)
                );
                topStart = mergedInterval.start;
                topEnd = mergedInterval.end;
            }else {
                result.add(new Interval(topStart, topEnd));
                topStart = currentI.start;
                topEnd = currentI.end;
            }
        }
        result.add(new Interval(topStart, topEnd));
        return result;
    }

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

        @Override
        public String toString(){
            return "( " + start + " , " + end + " )";
        }
    }

    public static void main(String[] args){
        MergeIntervals mergeIntervals = new MergeIntervals();
        List<Interval> intervals = new ArrayList<>();
        intervals.add(mergeIntervals.new Interval(1,3));
        intervals.add(mergeIntervals.new Interval(2,6));
        intervals.add(mergeIntervals.new Interval(8,10));
        intervals.add(mergeIntervals.new Interval(15,18));

        List<Interval> mergedIntervals = mergeIntervals.merge(intervals);
        for(Interval interval: mergedIntervals){
            System.out.println(interval);
        }
    }
}
