Showing posts with label Sort. Show all posts
Showing posts with label Sort. Show all posts

Sunday, August 23, 2015

MJ [25] Bucket Sort

Ref
[1] http://www.sanfoundry.com/cpluscplus-program-implement-bucket-sort/
[2] http://www.geeksforgeeks.org/bucket-sort-2/
Posted by at No comments:
Labels: , ,

Friday, August 7, 2015

LeetCode [253] Meeting Rooms II

 253. Meeting Rooms II

Medium

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//C++: 584ms
bool myComp(const Interval &a, const Interval &b){
    return (a.start<b.start);
}
class Solution {
public:
    int minMeetingRooms(vector<interval>& intervals) {
        int rooms = 0;
        priority_queue<int> pq;//prioritize earlier ending time
        sort(intervals.begin(), intervals.end(), myComp);
        for(int i=0; i<intervals.size(); ++i){
            while(!pq.empty() && -pq.top()<intervals[i].end) pq.pop();
            pq.push(-intervals[i].end);
            rooms = max(rooms, (int)pq.size());
        }
        return rooms;
    }
};

//C++
//C++: 616ms
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        map<int, int> changes;//sorted by keys.
        for(auto i:intervals){
            changes[i.start]++;
            changes[i.end]--;
        }
        int rooms = 0, min_rooms = 0;
        for(auto c:changes){
            rooms += c.second;
            min_rooms = max(min_rooms, rooms);
        }
        return min_rooms;
    }
};

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int i=0; i<intervals.length; ++i){
            map.put(intervals[i][0], map.getOrDefault(intervals[i][0], 0)+1);
            map.put(intervals[i][1], map.getOrDefault(intervals[i][1], 0)-1);
        }
        int rooms = 0, minRooms = 0;
        for(Map.Entry<Integer,Integer> e : map.entrySet()){
            rooms += e.getValue();
            minRooms = Math.max(minRooms, rooms);
        }
        return minRooms;
    }
}

第二轮，白人manager，刷题网尔无伞的变形，要求自定义输入的数据，并且返回一个schedule（自定义输出格式）。我这轮执着于原题解法，总是想用priority queue，写的磕磕巴巴，面完回去想了想用dict记录每个房间和能放在这个房间的所有会议起始时间就行。。最后问了问怎么测试，测试数据从哪来。。等等，就到时间了，这轮应该是给了个比较差的feedback。

Posted by at No comments:
Labels: , , , ,

LeetCode [252] Meeting Rooms

 252. Meeting Rooms

Easy

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

 

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

 

Constraints:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti < endi <= 106
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//C++: 588ms
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool comp(const Interval &a, const Interval &b){
    return a.start<b.start;
} 

class Solution {
public:
    bool canAttendMeetings(vector<interval>& intervals) {
        sort(intervals.begin(), intervals.end(), comp);
        for(int i=1; i<intervals.size(); ++i){
            if(intervals[i].start<intervals[i-1].end) return false;
        }
        return true;
    }
};

YMSF

第一轮： 蠡口兒吴饵的变种。给一列interval 和一个新的interval，看新的interval有没有和之前的有conflict。 Followup 是 如果给的一列的interval是sorted，如何提高时间复杂度。 当时的想法是binary search.

应该是sorted by start time吧 然后binary search找这个interval应该插入到哪里，找到以后看它和它前面的和后面的intervals是否有相交。

Posted by at No comments:
Labels: , , , ,

Saturday, August 1, 2015

LeetCode [242] Valid Anagram

 242. Valid Anagram

Easy

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool isAnagram(string s, string t) {
        if((int)s.size()!=(int)t.size()) return false;
        int hash[26] = {0};
        for(int i=0; i<(int)s.size(); ++i){
            hash[s[i]-'a']++;
            hash[t[i]-'a']--;
        }
        for(int i=0; i<26; ++i){
            if(hash[i]) return false;
        }
        return true;
    }
};


1
2
3
4
5
6
7
8
class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s==t;
    }
};
Posted by at No comments:
Labels: , , , ,

Saturday, July 11, 2015

LeetCode [57] Insert Interval

57. Insert Interval
Hard
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
========
* use upper_bound to find the the range of merged interval
* the sort in the last step can be optimized by delicate insertions.
========
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution
{
  public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        vector<vector<int>> ret;
        int lb, ub;

        //find lower bound of merged new interval
        // |--prev(lv)--|     |--lv--|
        //          |--newIntv--|
        //lv is the first interval pass newInterval[0]. 
        //INT_MAX makes upper_bound return a vector with strickly greater first value
        auto lv = upper_bound(intervals.begin(), intervals.end(), vector<int>{newInterval[0], INT_MAX});
        if (lv == intervals.begin())
        {
            lb = newInterval[0];
        }
        else
        {
            lv = prev(lv);
            if ((*lv)[1] >= newInterval[0])
                lb = (*lv)[0];
            else
                lb = newInterval[0];
        }

        //find upper bound of the merged interval
        // |--prev(uv)--|             |--uv--|
        //          |--newIntv--|
        //lv is the first interval pass newInterval[1]. 
        auto uv = upper_bound(intervals.begin(), intervals.end(), vector<int>{newInterval[1], INT_MAX});
        if (uv == intervals.begin())
        {
            ub = newInterval[1];
        }
        else
        {
            uv = prev(uv);
            ub = max(newInterval[1], (*uv)[1]);
        }

        for(auto i:intervals)
        {
            if(i[1]<lb || i[1]>ub) ret.push_back(i);
        }
        ret.push_back(vector<int>{lb, ub});
        sort(ret.begin(), ret.end());

        return ret;
    }
};
======== legend ======== 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//C++: method1 596ms
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool compare(const Interval &a, const Interval &b){
  return a.start<b.start;
}
  
class Solution {
public:
    vector<interval> merge(vector<interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<interval> res;
        int n = intervals.size();
        int i = 0;
        while(i<n){
            int j = i+1;
            while(j<n && intervals[i].end>=intervals[j].start){
                intervals[i].end = max(intervals[i].end, intervals[j].end);
                j++;
            }
            res.push_back(intervals[i]);
            i = j;
        }
        return res;
    }
    vector<interval> insert(vector<interval>& intervals, Interval newInterval) {
        intervals.push_back(newInterval);
        return merge(intervals);
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<interval> insert(vector<interval>& intervals, Interval newInterval) {
        vector<interval> res;
        int n = intervals.size();
        int i=0;

        while(i<n && intervals[i].end<newInterval.start){
            res.push_back(intervals[i++]);
        }

        if(i==n || newInterval.end<intervals[i].start){
            res.push_back(newInterval);
        }else{
            int start = i++;
            while(i<n && newInterval.end>=intervals[i].start) i++;
            int end = i-1;

            newInterval.start = min(newInterval.start, intervals[start].start);
            newInterval.end = max(newInterval.end, intervals[end].end);
            res.push_back(newInterval);
        }

        while(i<n) res.push_back(intervals[i++]);
        return res;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<interval> insert(vector<interval> &intervals, Interval newInterval) {
        vector<interval> res;
        int n = intervals.size();
        if(n==0){res.push_back(newInterval); return res;}

        int i=0;
        vector<interval>::iterator it=intervals.begin();
        //|---0--| ... |---i--|
        //                       |----newInt------|
        while(i<n && intervals[i].end<newInterval.start){
            res.push_back(intervals[i++]);
        }
        
        //newIntervals is left alone
        if(i==n){
            res.push_back(newInterval); 
            return res;
        }
        
        //                          |----i-----|
        //|-----newInt-------|
        if(newInterval.end<intervals[i].start){
            res.push_back(newInterval);
            res.insert(res.end(), it+i, it+n);
            return res;
        }

        //          |----i-----|       |----i-----|
        //|-----newInt---|        or        |-----newInt-------| 
        //a                    b       a                       b
        int a = min(intervals[i].start, newInterval.start);
        int b = max(intervals[i].end, newInterval.end);            
        for(++i;i<n;++i){
            if(b<intervals[i].start){
                Interval intv(a, b);
                res.push_back(intv);
                res.insert(res.end(), it+i, it+n);
                break;
            }else{
                b = max(intervals[i].end, b);
            }
        }
        if(i==n){
            Interval intv(a, b);
            res.push_back(intv);                            
        }

        return res;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//Java
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        int i = 0;
        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> list = new ArrayList<>();

        while(i<n && intervals[i][1]<start){
            list.add(intervals[i]);
            i++;
        }

        while(i<n && intervals[i][0]<=end){
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[]{start, end});

        while(i<n){
            list.add(intervals[i]);
            i++;
        }
        
        int[][] res = new int[list.size()][2];
        for(int k=0; k<list.size(); ++k){
            res[k] = list.get(k);
        }
        return res;
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        List<int[]> list = new ArrayList<>();
        int l = lastEndBeforeNewStart(intervals, newInterval[0]);
        int r = firstStartBeforeNewEnd(intervals, newInterval[1]);
        int i = 0;
        while(i<=l){
            list.add(intervals[i++]);
        }
        int start = newInterval[0], end = newInterval[1];
        while(i<r){
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[]{start, end});
        while(i<n){
            list.add(intervals[i++]);
        }
        return list.toArray(new int[0][]);
    }

    int lastEndBeforeNewStart(int[][] intervals, int newStart){
        int n = intervals.length;
        int l = 0, r = n-1;
        while(l<=r){
            int m = (l+r)/2;
            if(intervals[m][1]<newStart && (m==r || intervals[m+1][1]>=newStart)){
                return m;
            }else if(intervals[m][1]<newStart){
                l = m+1;
            }else{
                r = m-1;
            }
        }
        return -1;
    }

    int firstStartBeforeNewEnd(int[][] intervals, int newEnd){
        int n = intervals.length;
        int l = 0, r = n-1;
        while(l<=r){
            int m = (l+r)/2;
            if(intervals[m][0]>newEnd && (m==l||intervals[m-1][0]<=newEnd)){
                return m;
            }else if(intervals[m][0]>newEnd){
                r = m-1;
            }else{
                l = m+1;
            }
        }
        return n;
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0], end = newInterval[1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int[] i : intervals){
            int u = i[0], v = i[1];
            map.put(u, v);
        }

        //[l, r], find max l s.t. l<=start
        Map.Entry<Integer, Integer> lEntry = map.floorEntry(start);
        if(lEntry!=null && lEntry.getValue()>=start){
            start = lEntry.getKey();
        }

        //[l, r] find min l s.t. l<=end
        Map.Entry<Integer, Integer> rEntry = map.floorEntry(end);
        if(rEntry!=null && rEntry.getValue()>=end){
            end = rEntry.getValue();
        }

        Map<Integer, Integer> submap = map.subMap(start, true, end, true);
        Set<Integer> set = new HashSet<>(submap.keySet());
        map.keySet().removeAll(set);
        map.put(start, end);

        int[][] ret = new int[map.size()][2];
        int i = 0;
        for(Map.Entry<Integer, Integer> en : map.entrySet()){
            ret[i][0] = en.getKey();
            ret[i][1] = en.getValue();
            i++;
        }
        
        return ret;
    }
}
Posted by at No comments:
Labels: ,
Subscribe to: Comments (Atom)