Split Array into Consecutive Subsequences

LeetCode Q 659 - Split Array into Consecutive Subsequences

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1: Input: [1,2,3,3,4,5] ; Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5

Example 2: Input: [1,2,3,3,4,4,5,5] ; Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5

Example 3: Input: [1,2,3,4,4,5] ; Output: False

Note: The length of the input is in range of [1, 10000]

Solution

Whenever we encounter a number, we do the dicision according to the following three cases.

• Case 1 : num == pq.peek().end, we offer a new interval (num, num) to pq => #1
• Case 2 : num == pq.peek().end+ 1, we poll a interval prev, offer a new interval (prev.start, num) => #2
• Case 3 : num > p1.peek().end + 1, we keep abandoning intervals (if the length of the interval to abandon is smaller than 3, return false) until we could reduce to case 1 or case 2 => #3

The order of 3 cases above matters. For easier implementation, Case 3 should be checked first.

In the priority queue, all intervals are sorted by end increasingly, if there is a tie, we sort them by size increasingly.

Code:

public boolean isPossible(int[] nums) {

	PriorityQueue<Interva> pq = new PriorityQueue<>( new Comparator<Interval> () {
		public int compare (Interval a, Interval b) {
			if (a.end != b.end)
				return b.end - a.end;
			return a.length - b.length;
		}	
	});

	for (int num: nums) {
	
		while (!pq.isEmpty() && pq.peek().end + 1 < num) {
			if (pq.poll().length < 3)
				return false;
		} 

		if (pq.isEmpty() || pq.peek().end == num) {
			pq.offer(new Interval(num, num));
		} else { // pq.peek().end + 1 = num
			pq.offer(new Interval(pq.poll().start, num));
		}	
	}

	while (pq.isEmpty()) {
		if (pq.poll().length < 3)
			return false;
	}

	return true;
}

class Interval {
	int start, end, length;
	publit Interval (int start, int end) {
		this.start = start; this.end = end;
		this.length = end - start + 1;
	}
}