1. Runtime Distribution

2. Submission Details

3. Description

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

4. Example

Suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

List intervals;

public SummaryRanges() {
	intervals = new ArrayList();
}

public void addNum(int val) {
	int pos = binarySearch(val);

	if (pos < 0) {
		if (intervals.size() > 0 && val == intervals.get(0).start - 1) {
			intervals.get(0).start = val;
		} else {
			intervals.add(0, new Interval(val, val));
		}
	} else {
		if (val == intervals.get(pos).end + 1) {
			intervals.get(pos).end = val;
		} else if (val > intervals.get(pos).end + 1) {
			intervals.add(pos + 1, new Interval(val, val));
			pos++;
		}
		if (pos + 1 < intervals.size() && intervals.get(pos).end + 1 == intervals.get(pos + 1).start) {
			intervals.get(pos).end = intervals.get(pos + 1).end;
			intervals.remove(pos + 1);
		}
	}
}

public int binarySearch(int n) {
	int end = intervals.size() - 1;
	if (end < 0) {
		return -1;
	}

	int start = 0;
	int mid = 0;
	while (start <= end) {
		mid = ((end - start) >> 1) + start;
		if (n < intervals.get(mid).start) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return end;
}

public List getIntervals() {
	return intervals;
}

[/restab]
[restab title="Java TreeMap"]

TreeMap treeMap;

public SummaryRanges() {
	treeMap = new TreeMap<>();
}

public void addNum(int val) {
	if (treeMap.containsKey(val)) {
		return;
	}

	Integer left = treeMap.lowerKey(val);
	Integer right = treeMap.higherKey(val);

	if (left != null && right != null && treeMap.get(left).end + 1 == val && val + 1 == right) {
		treeMap.get(left).end = treeMap.get(right).end;
		treeMap.remove(right);
	} else if (right != null && val + 1 == right) {
		treeMap.put(val, new Interval(val, treeMap.get(right).end));
		treeMap.remove(right);
	} else if (left != null && treeMap.get(left).end + 1 >= val) {
		treeMap.get(left).end = Math.max(treeMap.get(left).end, val);
	} else {
		treeMap.put(val, new Interval(val, val));
	}
}

public List getIntervals() {
	return new ArrayList<>(treeMap.values());
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

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

public class LeetCode0352 {

	class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	List intervals;

	public LeetCode0352() {
		intervals = new ArrayList();
	}

	public void addNum(int val) {
		int pos = binarySearch(val);

		if (pos < 0) {
			if (intervals.size() > 0 && val == intervals.get(0).start - 1) {
				intervals.get(0).start = val;
			} else {
				intervals.add(0, new Interval(val, val));
			}
		} else {
			if (val == intervals.get(pos).end + 1) {
				intervals.get(pos).end = val;
			} else if (val > intervals.get(pos).end + 1) {
				intervals.add(pos + 1, new Interval(val, val));
				pos++;
			}
			if (pos + 1 < intervals.size() && intervals.get(pos).end + 1 == intervals.get(pos + 1).start) {
				intervals.get(pos).end = intervals.get(pos + 1).end;
				intervals.remove(pos + 1);
			}
		}
	}

	public int binarySearch(int n) {
		int end = intervals.size() - 1;
		if (end < 0) {
			return -1;
		}

		int start = 0;
		int mid = 0;
		while (start <= end) {
			mid = ((end - start) >> 1) + start;
			if (n < intervals.get(mid).start) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		return end;
	}

	public List getIntervals() {
		return intervals;
	}
}

[/restab]
[restab title="Java TreeMap"]

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class LeetCode0352 {

	class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	TreeMap treeMap;

	public LeetCode0352() {
		treeMap = new TreeMap<>();
	}

	public void addNum(int val) {
		if (treeMap.containsKey(val)) {
			return;
		}

		Integer left = treeMap.lowerKey(val);
		Integer right = treeMap.higherKey(val);

		if (left != null && right != null && treeMap.get(left).end + 1 == val && val + 1 == right) {
			treeMap.get(left).end = treeMap.get(right).end;
			treeMap.remove(right);
		} else if (right != null && val + 1 == right) {
			treeMap.put(val, new Interval(val, treeMap.get(right).end));
			treeMap.remove(right);
		} else if (left != null && treeMap.get(left).end + 1 >= val) {
			treeMap.get(left).end = Math.max(treeMap.get(left).end, val);
		} else {
			treeMap.put(val, new Interval(val, val));
		}
	}

	public List getIntervals() {
		return new ArrayList<>(treeMap.values());
	}
}

[/restab]
[/restabs]