Description
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
Note:
- You must return the copy of the given head as a reference to the cloned list.
Examples
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
Answer
First sort the input in ascending order then traverse the input and compare all the intervals with the biggest/smallest intrerval. if has cross part then modify. if not then push the interval into the result set.
Time Complexity
O(n)
Code
C++
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
if(intervals.size() == 0 || intervals[0].size() <= 1) return inetervals;
vector<vector<int>> res;
sort(intervals.begin(), intervals.end());
res.push_back(intervals[0]);
for(int i = 0; i < n; ++i)
{
if(intervals[i][0] <= res.back()[1])
res.back()[1] = max(intervals[i][1], res.back()[1]);
else
res.push_back(intervals[i]);
}
return res;
}
};
